| Week | Topic | Subtopic | Reading |
|---|---|---|---|
| 1 | Introduction to Algorithms | Th 1/26 - Stable marriage (JC) | KT 1.1 Man-optimality proof |
| 2 | Intro, Greedy Algs | Tu 1/31 - overview of algorithm design, GCD alg (SK) Th 2/2 - GCD alg, interval scheduling (SK) |
KT 4.1 |
| 3 | Greedy Algs | Tu 2/7 - scheduling to minimize lateness; to maximize profit (SK) Th 2/9 - minimum spanning trees (SK) |
KT 4.2; Max Profit Scheduling KT 4.5 and 4.6 |
| 4 | Greedy Algs | Tu 2/14 - caching (JC) Th 2/16 - shortest paths (SK) |
KT 4.3 KT 4.4 Caching slides |
| 5 | Graph Algs | Tu 2/21 - BFS, DFS and edge connectivity (SK) Th 2/23 - Strong connectivity (SK) |
KT 3.4, KT 3.5 Properties of DFS from CLRS Notes on bridges SCC notes from CLRS |
| 6 | Graph Algs | Tu 2/28 - Strong connectivity (SK) Th 3/2 - review session (JC) |
Notes on Menger's Thm (Errata: paths P' and P'' switched in the bottom figure) Review problems |
| 7 | -- | Tu 3/7 - in-class exam Th 3/9 - guest lecture on distributed algorithms (David Harris) |
|
| 8 | Dynamic Programming | Tu 3/14 - Pi Day Snow Day Th 3/16 - Weighted Interval Scheduling, Knapsack (SK) |
KT 6.1 |
| Spring Break | -- | Enjoy your break! | -- |
| 9 | Dynamic Programming | Tu 3/28 - Bellman-Ford; Floyd-Warshall (SK) Th 3/30 - Segmented Least Squares (SK) |
KT 6.8 CLRS notes on Floyd-Warshall KT 6.3 |
| 10 | Dynamic Programming | Tu 4/4 - negative cycles; sequence alignment (SK) Th 4/6 - edit distance (JC) |
KT 6.5-6.7 |
| 11 | Network Flows | Tu 4/11 - (SK) Th 4/13 - (SK) |
Wayne's Network Flow notes KT 7.1, 7.2 |
| 12 | -- | Tu 4/18 - review session (JC) Th 4/20 - in-class exam |
|
| 13 | Network Flows | Tu 4/25 - bipartite matching (SK) Th 4/27 - network flow applications (SK) |
KT 7.5 |
| 14 | NP completeness | Tu 5/2 - Reductions (JC) Th 5/4 - NP-completeness (SK) |
KT 8.1, 8.2 NP-completeness handout |
| 15 | NP completeness | Tu 5/9 - TBD Th 5/11 - Final exam review |
|
| Final Exam | Th 5/18 4-6pm |