15-112: Fundamentals of Programming and Computer Science
Class Notes: Efficiency

• Add these topics:
  
  
  • Input Size
    
    • For list L: n = # of elements in the list == len(L)
    • For integer n: we generally use n in 112, but technically should use size(n) == # of bits to represent n = log2(n)
  
  
  • Sorting Links
    
    • Wikipedia page on Sorting
    • David Eck's xSortLab applet (or you might try this jar file )
    • Our sorting sample code (You need to be able to write all of this from scratch!)
    • Excellent sorting animation website
    • Sorting algorithm animation video (15 algorithms in 6 minutes)
    • Even more sorting algorithm animations
  
  
  • BubbleSort
    You are responsible for writing (from scratch), understanding, and analyzing SelectionSort, BubbleSort, and MergeSort, and any reasonable variations of those. See here.
    
    
  • Sort Properties
    
    • Time Complexity (best, average, and worst cases). Note: in 112, we mostly prove best and worst cases.
    • Space Complexity (best, average, and worse cases).
    • In-Place (Uses O(1) space; ie, constant-sized memory (not counting the input))
    • Stable (maintains relative order of equal values)
    • Adaptive (recognizes pre-sorted lists)
    • Comparison-Based. Note: best-possible comparison-based algorithm is O(nlogn)
    • Serial or Parallel. Note: we only consider serial sorts in 112.
    • Implementation Details
      • Iterative vs Recursive
      • Destructive vs Nondestructive


• Omit these topics:
  • Omit example #4 (isPrime(nthHappyNumber(n)))
  • Omit example #6 (Sum of Prime Factors)