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