15-211 topics

This is a list of topics we have covered in 15-211, as complete as I can remember. Asterisks mark topics with cursory coverage. You needn't feel like you completely understand the starred topics; knowing them fuzzily should be enough.

• C++ stuff
  • recursion
  • pointers
  • classes
  • memory allocation
  • constructors and destructors
  • call-by-value and call-by-reference
  • inheritance
  • virtual functions
• Program analysis
  • invariants
  • big-O, Theta, and Omega notation
  • recurrences
• Algorithmic techniques
  • divide and conquer
  • dynamic programming and memoization
• Arrays
  • Searching
    • binary search
    • sequential search
  • Sorting
    • lower bound for comparison sorting
    • selection sort and insertion sort
    • quicksort and mergesort
    • heapsort
    • bucket sort and radix sort
  • Median computation (with quickselect)
• Lists
  • stacks
  • queues
  • list functions
• Trees
  • traversals (inorder, preorder, postorder)
  • binary search trees
  • balanced search trees
    • 2-3 trees
    • AVL trees *
  • tries
  • heaps
• Hash tables
  • hash functions
  • hash tables
  • collision techniques
    • separate chaining
    • linear probing
    • double hashing
  • extensible hashing (with doubling array)
• Graphs
  • breadth-first search
  • depth-first search
  • priority-first search
  • minimum spanning tree
  • all-pairs shortest paths
  • minimum matching *
  • transitive closure *
• Game playing
  • game trees
  • alpha-beta search *
• Ziv-Lempel compression
• Finite automata
  • finite automata
  • Knuth-Morris-Pratt string matching
  • regular languages
  • regular expressions