Topics
- Part I. Greedy Algorithms. Divide and Conquer. Dynamic Programming. Random Sampling.
- Part II. Online Data Structures (e.g. Union-Find) with Amortized Analysis. Text Compression (e.g. Lempel-Ziv). Bipartite Matchings. Flows. Linear Programming (Simplex). Markov Chain Monte Carlo (without runtime analysis).
- Part III (Time Allowing). Clustering. Beyond Worst-Case Models. Approximation Algorithms. Energy Minimization. Stable Matching. etc.
Lectures
| # | Date | Topic | Notes |
|---|---|---|---|
| 1 | Sep 10 (Thurs) | Part I | |
| 2 | Sep 15 (Tues) | ||
| 3 | Sep 17 (Thurs) | ||
| 4 | Sep 22 (Tues) | ||
| 5 | Sep 24 (Thurs) | ||
| 6 | Sep 29 (Tues) | ||
| 7 | Oct 01 (Thurs) | ||
| 8 | Oct 06 (Tues) | Part II (Tested on Midterm 2) | |
| 9 | Oct 08 (Thurs) | Midterm 1 | |
| 10 | Oct 13 (Tues) | ||
| 11 | Oct 15 (Thurs) | ||
| 12 | Oct 20 (Tues) | ||
| 13 | Oct 22 (Thurs) | ||
| 14 | Oct 27 (Tues) | ||
| 15 | Oct 29 (Thurs) | ||
| - | Nov 03 (Tues) | No Class (Election Day) | |
| 16 | Nov 05 (Thurs) | Midterm 2 | |
| 17 | Nov 10 (Tues) | Part III | |
| 18 | Nov 12 (Thurs) | ||
| 19 | Nov 17 (Tues) | ||
| 20 | Nov 19 (Thurs) | ||
| 21 | Nov 24 (Tues) | ||
| - | Nov 26 (Thurs) | No Class (Thanksgiving) | |
| 22 | Dec 01 (Tues) | ||
| 23 | Dec 03 (Thurs) | ||
| 24 | Dec 08 (Tues) | Course Recap (Reading Period) | |
| Dec 10 (Thurs) | No Class (Reading Period) | ||
| Dec 14 (Mon) | Final Exam |