| Date | Topic | Reading (CLRS) | Due |
1. | 08/28: | Intro & Admin. Karatsuba/Strassen. | | |
2. | 08/30: | Asymptotic analysis, solving recurrences | 1-4 | |
3. | 09/04: | Probabilistic analysis, Randomized Quicksort | 5,7 | Mini 1 due |
4. | 09/06: | Linear-time Selection (randomized and deterministic) | 9 | |
5. | 09/11: | Sorting/searching lower bounds | 8.1 | Hwk 1 due |
6. | 09/13: | Review | | |
7. | 09/18: | Tight upper/lower bounds II | | Mini 2 due |
8. | 09/20: | Amortized Analysis | 17 | |
9. | 09/25: | Search trees: B-trees, treaps | 12,18 | Hwk 2 pres |
10. | 09/27: | Hashing: universal and perfect hashing | 11 | |
11. | 10/02: | Radix sort, tries + QUIZ | 8 | Mini 3 due |
12. | 10/04: | Dynamic Programming | 15 | |
13. | 10/09: | Graph Algorithms I | 22,23 | Hwk 3 due |
14. | 10/11: | Graph Algorithms II | 21 | |
15. | 10/16: | Graph Algorithms III | 24,25 | |
16. | 10/18: | MIDTERM | | |
17. | 10/23: | Network Flows and Matchings I | 26 | Hwk 4 pres |
18. | 10/25: | Network Flows and Matchings II | | |
19. | 10/30: | Linear Programming | 29 | Mini 4 due |
20. | 11/01: | NP-Completeness I | 34 | |
21. | 11/06: | NP-Completeness II | | Hwk 5 due |
22. | 11/08: | Approximation Algorithms | 35 | |
23. | 11/13: | On-line algorithms+ QUIZ | | |
24. | 11/15: | Number-theoretic algs I | 31 | |
25. | 11/20: | Number-theoretic algs II | | Hwk 6 pres Mon/Tues |
26. | 11/27: | Fast Fourier Transform | 30 | |
27. | 11/29: | Machine Learning and Game Theory | | Mini 5 due |
28. | 12/04: | Game Theory II (zero-sum & general-sum games) | | |
29. | 12/06: | Fair division, envy-free cake-cutting | | Hwk 7 due |