CMU 15-451 (Algorithms), Fall 2004

Instructors: Avrim Blum, Manuel Blum

TAs: Doru Balcan, Nina Balcan, Jon Derryberry, Runting Shi


General info

We will be using the textbook "Introduction to Algorithms (Second Edition)" by Cormen, Leiserson, Rivest, and Stein.



Lecture notes

  1. 08/31:Intro & Admin. Karatsuba/Strassen.
    09/01: (recitation) Warmup problems.
  2. 09/02:Asymptotic analysis, solving recurrences.
  3. 09/07:Probabilistic analysis, Randomized Quicksort.
    09/08: (recitation) Insertion sort and inversions.
  4. 09/09:Linear-time Selection (randomized and deterministic).
  5. 09/14:Upper and lower bounds in simplified models of computation.
  6. 09/15: (recitation) Review + Coupon collector's problem.
  7. 09/16:Upper and lower bounds (II)
  8. 09/21:Amortized Analysis
  9. 09/22: (recitation) Amortized analysis + Practice Quiz.
  10. 09/23:Search trees: B-trees and treaps.
  11. 09/28:Radix sort, tries.
    09/29: (recitation) B-trees & treaps review. Adding auxiliary info to data structures.
  12. 09/30:Hashing.
  13. 10/05:Dynamic Programming.
    10/06: (recitation) Search trees vs hashing; another method for universal hashing.
  14. 10/07:DP contd; Graph Algorithms I: DFS and Topological Sorting.
  15. 10/12:Graph Algorithms II: shortest path, bottleneck path, Bellman-Ford.
    10/13: (recitation) All-pairs shortest paths: Matrix products, Floyd-Warshall.
  16. 10/14:Graph Algorithms III: Minimum spnning trees (Prim, Kruskal). Union-find.
  17. 10/21:Network Flows and Matchings I.
  18. 10/26:Network Flows and Matchings II.
  19. 10/28:Linear Programming.
  20. 11/02:NP-completeness I.
  21. 11/04:NP-completeness II.
  22. 11/09:NP-completeness III.
    11/10: (recitation) Circuit-SAT and 3-SAT..
  23. 11/11:Approximation Algorithms.
  24. 11/16:Online Algorithms.
  25. 11/18:Number theoretic algorithms I.
  26. 11/23:Number theoretic algorithms II.
  27. 11/30:Fast Fourier Transform (FFT).
    12/01: (recitation) More on Number Theory and FFT..
  28. 12/02:Fair division: fair and envy-free cake-cutting.
  29. 12/07:Intro to game theory.
  30. 12/09:Learning Finite-State Environments.