CMU 15-451 (Algorithms), Fall 2003

Instructors: Avrim Blum, Manuel Blum

TAs: Richard Dore, Taka Osogami, Jorge Vittes

General info

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



Lecture notes

  1. 08/26:Intro & Admin. Karatsuba/Strassen.
  2. 08/28:Asymptotic analysis, solving recurrences.
  3. 09/02:Probabilistic analysis, Randomized Quicksort.
  4. 09/04:Linear-time Selection (randomized and deterministic).
  5. 09/09:Upper and lower bounds I.
  6. 09/14:Upper and lower bounds II.
  7. 09/16:Amortized analysis.
  8. 09/18:Search trees: B-trees and treaps.
  9. 09/23:Radix sort, tries.
  10. 09/25:Hashing I: universal hashing.
  11. 09/30:Hashing II: perfect hashing.
  12. 10/02:Dynamic Programming.
  13. 10/07:Graphs and depth-first search.
  14. 10/08: (recitation) Topological sorting. Shortest paths (Dijkstra and Bellman-Ford algorithms).
  15. 10/09:MST (Prim, Kruskal), bottleneck path, union-find.
  16. 10/14:All-pairs shortest paths via matrix products, Floyd-Warshall.
  17. 10/21:Online algorithms.
  18. 10/22: (recitation) Midterm solutions.
  19. 10/23:Network flows and matchings I.
  20. 10/28:Network flows and matchings II.
  21. 10/30:Linear Programming.
  22. 11/04:NP-Completeness I.
  23. 11/05: (recitation) LP examples. NP-completeness.
  24. 11/06:NP-Completeness II.
  25. 11/11:Approximation Algorithms.
  26. 11/13:Number-theoretic algorithms I.
  27. 11/18:Number-theoretic algorithms II.
  28. 11/20:The Fast Fourier Transform.
  29. 11/25:FFT recap [ppt, ps] and Learning finite-state environments [ppt]. [math in ppt might not look right without texpoint fonts]
  30. 12/02:Game theory intro [ppt, ps]
  31. 12/04:Cake cutting.