CMU 15-451 (Algorithms), Fall 2007

Instructor: Avrim Blum

TAs: Michael Dinitz, Jiquan Ngiam, Aaron Roth, Samuel Wang

General info



Lecture notes (in pdf and txt) [The first 20 lectures]

  1. 08/28:Intro & Admin. Karatsuba/Strassen.
    08/29: (recitation) Warmup problems.
  2. 08/30:Asymptotic analysis, solving recurrences.
  3. 09/04:Probabilistic analysis, Randomized Quicksort.
    09/05: (recitation) Problems related to randomized quicksort, insertion sort.
  4. 09/06:Linear-time Selection (randomized and deterministic).
  5. 09/11:Concrete models and tight upper/lower bounds I.
    09/12: (recitation) Problems related to selection recurrence, getting upper/lower bounds in concrete models.
  6. 09/13:Optional review: hwk1, probability practice, coupon collector's problem. [more details]
  7. 09/18:Concrete models and tight upper/lower bounds II
    09/19: (recitation) Problems related to tight bounds, connection to minimax optimality in games.
  8. 09/20:Amortized Analysis
  9. 09/25:Search trees: B-trees and treaps.
    09/26: (recitation) B-tree example + go over practice quiz.
  10. 09/27:Universal and Perfect Hashing.
  11. 10/02:Digit-based sorting/data-structures (radix sort, tries).
  12. 10/04:Dynamic Programming.
  13. 10/09:Graph Algorithms I: DFS and Topological Sorting, DP algs for shortest paths (Bellman-Ford, Matrix, Floyd-Warshall).
  14. 10/11:Graph Algorithms II: Dijkstra, Prim, Kruskal.
  15. 10/16:Graph Algorithms III: Union-find.
  16. 10/23:Network Flows and Matchings I.
    10/24: (recitation) Examples of problems that can be solved using network flow.
  17. 10/25:Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow.
  18. 10/30:Linear Programming.
    10/31: (recitation) Examples of problems that can be solved using linear programming.
  19. 11/01:NP-completeness I.
  20. 11/06:NP-completeness II.
    11/07: (recitation) Examples of NP-completeness reductions: Integer Programming and 3-Coloring.
  21. 11/08:Approximation Algorithms.
  22. 11/13:Online Algorithms.
  23. 11/15:Number theoretic algorithms I.
  24. 11/20:Number theoretic algorithms II.
  25. 11/27:Fast Fourier Transform (FFT).
  26. 11/29:Intro to machine learning theory.
  27. 12/04:Intro to game theory.
  28. 12/06:Fair division: fair and envy-free cake-cutting.