CMU 15-451 (Algorithms), Fall 2011

Instructors: Avrim Blum and Manuel Blum

TAs: Nathaniel Barshay, Wendy Hu, B. Aditya Prakash, Zak Wise, and Lidong Zhou


General info


Minis


Homeworks


Lecture/recitation notes [The first 10 lectures] [Lectures 12-14]

  1. 08/30:Intro & Admin. Karatsuba/Strassen.
    08/31: (recitation) Warmup problems.
  2. 09/01:Asymptotic analysis, solving recurrences.
  3. 09/06:Probabilistic analysis, Randomized Quicksort.
    09/07: (recitation) Problems related to randomized quicksort, insertion sort.
  4. 09/08:Linear-time Selection (randomized and deterministic).
  5. 09/13:Comparison-based lower bounds for sorting.
    09/14: (recitation) Problems related to selection recurrence, upper/lower bounds in concrete models.
  6. 09/15:Concrete models and tight upper/lower bounds
  7. 09/20: Tight upper/lower bounds for matrix searching
    09/21: (recitation) radix sort
  8. 09/22:Amortized Analysis
  9. 09/27:Search trees: B-trees and treaps
    09/28: (recitation) B-tree and treap examples, treap analysis.
  10. 09/29: Result-checking: programs that check their work.
  11. 10/04:Universal and Perfect Hashing.
    10/05: (recitation) universal hashing recap, alternative hashing scheme, cryptographic hash functions, testing matrix multiplication.
  12. 10/06:Dynamic Programming.
  13. 10/11:Graph Algorithms I: DFS and Topological Sorting, DP algs for shortest paths (Bellman-Ford, Matrix, Floyd-Warshall).
    10/12: (recitation) Discuss practice midterm.
  14. 10/13:Graph Algorithms II: Dijkstra, Prim, Kruskal.
  15. 10/20:Graph Algorithms III: Union-find and planarity testing (notes cover only union-find).
    P.S. here is the original Hopcroft-Tarjan planarity-testing paper. (note the need to define O() and the basic model of computation in the intro. The key idea for the algorithm is given in section 4).
  16. 10/25:Network Flows and Matchings I.
    10/26: (recitation) Examples of problems that can be solved using network flow.
  17. 10/27:Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow.
  18. 11/01:Linear Programming.
    11/02: (recitation) Examples of problems that can be solved using linear programming.
  19. 11/03:NP-completeness I.
  20. 11/08:NP-completeness II.
    11/09: (recitation) Examples of NP-completeness reductions: Integer Programming and 3-Coloring.
  21. 11/10: Beyond NP-completeness (see notes above, plus material we won't test on PSPACE, Savitch's theorem, alternation)
  22. 11/15:Approximation Algorithms.
  23. 11/17:Online Algorithms.
  24. 11/22:Number theoretic algorithms I: Pollard's rho algorithm.
  25. 11/29:Number theoretic algorithms II: Lattice basis reduction. [LLL paper]
    11/30: (recitation) Number theory basics, Extended GCD, inverses, Fermat's little thm, Euler's them.
  26. 12/01:Fast Fourier Transform (FFT).
  27. 12/06:Intro to game theory.
    12/07: (recitation) Course recap.
  28. 12/08:Intro to machine learning theory.