CMU 15-451 (Algorithms), Fall 2000

Instructors: Avrim Blum, Danny Sleator

TAs: Mike Bowling, Nick Hopper, Dan Tennant


Heads-up: The Final is on Monday Dec 18, 8:30am-11:30am in PH100. You may use 1 sheet of notes (but the final is not open book). Last year's final is available below.

Course information


Assignments


Other Handouts and Practice problems


Lecture Notes

Here are some lecture notes for your convenience. Please feel free to email the instructor if you notice any mistakes in them. We are providing these for any students interested.

  1. 08/29:Intro & Admin. Karatsuba multiplication.
  2. 08/31:Asymptotic analysis. Solving recurrences.
  3. 09/05:Probabilistic analysis. Randomized Quicksort.
  4. 09/07:Linear-time selection (randomized and deterministic).
  5. 09/12:Lower bounds for comparison sorting.
  6. 09/14:Balanced search trees I: B-trees.
  7. 09/19:Amortized analysis.
  8. 09/21:Splay Trees.
  9. 09/26:Tries and Radix Sort.
  10. 09/28:Hashing I: basics + universal hashing.
  11. 10/03:Hashing II: universal and perfect hashing.
  12. 10/05:Dynamic Programming.
  13. 10/10:Graph Algorithms I.
  14. 10/12:Binomial and Fibonacci heaps.
  15. 10/17:Midterm.
  16. 10/19:Graph algs II: Dijkstra, Prim, Kruskal.
  17. 10/24:Union-find.
  18. 10/26:Network flow and bipartite matching.
  19. 10/31:Network flow, contd: more examples + Edmonds-Karp.
  20. 11/02:Linear Programming.
  21. 11/07:NP-Completeness.
  22. 11/09:NP-Completeness, contd.
  23. 11/14:DFT and FFT (postscript).
  24. 11/16:Number-theoretic algs I.
  25. 11/21:Number-theoretic algs II.
  26. 11/28:Approximation algorithms.
  27. 11/30:Zero Knowledge (postscript).
  28. 12/05:Competitive Algorithms: text and slides (PDF)
  29. 12/07:Online machine learning.
  30. 12/12:Summary.

Avrim Blum avrim+@cs.cmu.edu