CMU 15-451 (Algorithms), Fall 1999

Instructor: Avrim Blum

TAs: Shelby Davis, Orna Raz, Sanjit Seshia, Dan Tennant

Course information

• Syllabus and contact information
• Schedule
• Course newsgroup: cmu.cs.class.cs451

Assignments

• Assignment 1 is due Thursday September 9. Solutions
• Assignment 2. Solutions.
• Assignment 3. Solutions.
  See the bboard for a clarification on problem 1.
• Assignment 4. Solutions.
• Assignment 5. Solutions.
• Assignment 6. Solutions.
• Assignment 7. Solutions to questions from last year's final on this assignment. See bboard for solution to question 1.

Other Handouts and Practice problems

• Homework template: Typed homework is not required, but we don't discourage it.
  LaTeX source and Result in postscript
• Last semester's quiz 1 and solutions.
• Last semester's midterm and solutions.
• Last semester's quiz 2 and solutions. Note: last semester we did number-theoretic algorithms earlier and NP-completeness later. So, you don't need to worry about question 3 (though parts a and b are motivated by the FFT). On the other hand, you should make sure to study NP-completeness even though it's not on the sample quiz.
• Last semester's final exam.

Lecture Notes

1. 08/24:Intro & Admin. Karatsuba multiplication.
2. 08/26:Asymptotic analysis. Solving recurrences.
3. 08/31:{worst,average,expected} case. Probabilistic analysis. Randomized Quicksort.
4. 09/02:linearity of expectation. Linear-time median-finding.
5. 09/07:Lower bounds for comparison sorting. Radix sort.
6. 09/09:Universal Hashing.
7. 09/14:Perfect Hashing and quiz.
8. 09/16:Simple binary search trees and B-trees.
9. 09/21:2-3-4 trees, skip-lists, and Tries.
10. 09/23:Amortized analysis.
11. 09/28:Dynamic Programming.
12. 09/30:Graph algorithms: coloring, DFS, BFS, Bellman-Ford.
13. 10/05:Graph algorithms: Shortest Paths (Dijkstra's alg) and MST (Prim and Kruskal).
14. 10/07: MIDTERM
15. 10/12:Union-Find.
16. 10/14:Complexity Theory: P, NP, and NP-Completeness.
17. 10/19:Complexity Theory: NP-Completeness and Reductions.
18. 10/21:Max-flow, min-cut, maximum matchings.
19. 10/26:Max-flow contd. Edmonds-Karp, applications.
20. 10/28:Linear Programming.
21. 11/02:The Fast Fourier Transform (FFT).
22. 11/04:The FFT contd (and quiz).
23. 11/09:Number-theoretic algs I.
24. 11/11:Number-theoretic algs II.
25. 11/16:Global min cuts.
26. 11/18:Online algorithms in machine learning, and the min-max theorem.
27. 11/23:Online algorithms: rent-or-buy, pursuer-evader, paging.
28. 11/30:Approximation Algorithms.
29. 12/02:Summary and overview.