| Date | Topic | Reading | Homework |
|---|---|---|---|
| Wed Sep 9 | Welcome. Course overview. Introduce stable marriage. | HW0 Out (Due 9/16) |
|
| Mon Sep 14 | Finish stable marriage, the deferred-acceptance algorithm. Introduce greedy algs: interval partitioning. |
KT 1.1 Review KT 1.2, 2.*, 3.* (These should be familiar) |
|
| Wed Sep 16 | More greedy algorithms: minimum-lateness scheduling, Dijkstra's algorithm. | KT 4.1-4.6 | HW0 Due HW1 Out (Due 9/30) |
| Mon Sep 21 | Finish greedy algorithms: Huffman coding. | KT 4.8 | |
| Wed Sep 23 | Divide and conquer: Solving recurrences, integer multiplication | ||
| Mon Sep 28 | Divide and conquer: Fast Fourier Transform (FFT) | KT 5.5-5.6 KT 5.1-5.4 |
|
| Wed Sep 30 | Dynamic programming: weighted interval scheduling, segmented least squares | HW1 Due HW2 Out (Due 10/14) |
|
| Mon Oct 5 | Dynamic programming: RNA folding, longest common subsequence | KT 6.6-6.7 (I posted this late, you can read these for Wed) |
|
| Wed Oct 7 | Network Flow: Ford-Fulkerson, Max-Flow Min-Cut Duality | KT 7.1-7.2 | |
| Mon Oct 12 | No class (Columbus Day) | --- | |
| Wed Oct 14 | Network Flow: Capacity Scaling, Applications | KT 7.3, 7.5-7.7 KT 7.8-7.12 |
HW2 Due HW3 Out (Due Wed 10/28) |
| Mon Oct 19 | First Midterm (In Class) | ||
| Wed Oct 21 | Linear Programming | Jeff Erickson's LP Notes | |
| Mon Oct 26 | Linear Programming: The Simplex Algorithm | Jeff Erickson's Simplex Notes | |
| Wed Oct 28 | Linear programming: Duality | HW3 Due HW4 Out (Due Fri, 11/13) |
|
| Mon Nov 2 | Randomized algorithms | LLM Chapters 14-16 KT 13.1-13.3 |
|
| Wed Nov 4 | Randomized algorithms | LLM Chapter18 KT 13.5-13.7 |
|
| Mon Nov 9 | Randomized algorithms | LLM Chapter 19 | |
| Wed Nov 11 | No class (Veterans Day) | ||
| Fri Nov 13 | HW4 Due | ||
| Mon Nov 16 | Intractability: Reductions, NP-Completeness (Guest lecture by Mehraneh) | KT 8.1-8.4 | |
| Wed Nov 18 | Intractability: Cook-Levin Theorem, Approximation (Guest lecture by Rajmohan) | KT 8.5-8.8 KT 11.1, 11.2, 11.4, 11.6 |
|
| Thu Nov 19- Fri Nov 20 |
Midterm 2 (Take Home). 8:00am Thu through 11:59pm Fri. | ||
| Mon Nov 23 | Learning Algorithms: PAC learning | Jennifer Wortman Vaughan's Notes 2, 3, 4 |
|
| Wed Nov 25 | No class (Thanksgiving) | --- | |
| Mon Nov 30 | No-Regret Learning | No Regret Chapter (MW Survey might be helpful) |
HW5 Out (Due 12/9) |
| Wed Dec 2 | Zero-Sum Games, Boosting, and LP Duality | MW Survey Ch 3.1-3.3 | |
| Mon Dec 7 | Zero-Sum Games, Boosting, and LP Duality | Additional notes on Boosting | |
| Wed Dec 9 | Gradient Descent, Wrap-Up Last Class! |
Gradient Descent Notes | |
| Fri Dec 11 | HW5 Due |