CMU 15-451 (Algorithms), Fall 2003

Instructors: Avrim Blum, Manuel Blum

TAs: Richard Dore, Taka Osogami, Jorge Vittes

General info

• Course information
• Schedule (our final is Mon Dec 15, 8:30-11:30am, Wean 7500)
• The course bboards are: academic.cs.15-451 (for announcements) and academic.cs.15-451.discuss (for general discussion).

Minis

• Mini 1 [txt,ps, pdf]. Due midnight Sept 2.
• Mini 2 [txt]. Due midnight Sept 16.
• Mini 3 [txt]. Due midnight Sept 30.
• Mini 4 [txt]. Due midnight Oct 28.
• Mini 5 [ps]. Due midnight Nov 25. [solutions]

Homeworks

• Homework 1 [ps, pdf]. Due (in class) Sept 9. Solutions [ps, pdf].
• Homework 2 [ps, pdf]. Due Sept 23/24 (oral presentations). Solutions [ps, pdf].
• Homework 3 [ps, pdf]. Due (in class) Oct 7. Solutions [ps, pdf].
• Homework 4 [ps, pdf]. Due Oct 21/22 (oral presentations). Solutions [ps, pdf].
• Homework 5 [ps] Due (in class) Nov 4. Solutions [ps]
• Homework 6 [ps, pdf] Due Nov 18/19 (oral presentations). Solutions [ps]
• Homework 7 [ps, pdf]. Due (in class) Dec 4. Solutions [ps, pdf].

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.