15-451 Fall 2004 Schedule

Readings refer to chapters in CLRS.
DateTopicReading   Due
1. 08/31: Intro & Admin. Karatsuba/Strassen.
2. 09/02: Asymptotic analysis, solving recurrences 1-4
3. 09/07: Probabilistic analysis, Randomized Quicksort    5,7Mini 1 due
4. 09/09: Linear-time Selection (randomized and deterministic) 9
5. 09/14: Sorting/searching lower bounds 8.1 Hwk 1 due
6. 09/16: Tight upper/lower bounds
7. 09/21: Amortized Analysis 17 Mini 2 due
8. 09/23: Search trees: B-trees, treaps 12,18
9. 09/28: Radix sort, tries + QUIZ 8Hwk 2 pres
10. 09/30: Hashing (universal & perfect hashing)11
11. 10/05: Dynamic Programming15Mini 3 due
12. 10/07: Graph Algorithms I22,23
13. 10/12: Graph Algorithms II21Hwk 3 due
14. 10/14: Graph Algorithms III24,25
15. 10/19: MIDTERM
16. 10/21: Network Flows and Matchings I26
17. 10/26: Network Flows and Matchings IIHwk 4 pres
18. 10/28: Linear Programming29
19. 11/02: NP-Completeness I34Mini 4 due
20. 11/04: NP-Completeness II
21. 11/09: NP-Completeness III35Hwk 5 due
22. 11/11: Approximation Algorithms
23. 11/16: On-line algorithms31
24. 11/18: Number-theoretic algs I+ QUIZ
25. 11/23: Number-theoretic algs II30Hwk 6 pres Mon and Tues
26. 11/30: Number-theoretic algs III (FFT)
27. 12/02: Fair division, envy-free cake-cuttingMini 5 due
28. 12/07: Game Theory (zero-sum, general-sum games, Braess paradox)
29. 12/09: Machine learning algorithmsHwk 7 due