| Week | Topic | Subtopic | Reading |
|---|---|---|---|
| 1 | Introduction to Algorithms | Stable Marriage (SK, JC) Intro to graphs (JC) |
KT 1.1 Man-optimality proof |
| 2 | Graphs: connectivity | BFS, DFS (JC) 2-edge connectivity (JC) |
KT 3.2-3.4 Lecture slides Old notes on bridges Properties of DFS Proof of Menger's Theorem |
| 3 | Graphs | Strongly Connected Components (SK) MSTs (SK) |
CLRS on SCC KT 4.5 |
| 4 | Greedy Algs for Graphs | (Snow Day) MSTs, Dijkstra's (JC) |
KT 4.4 |
| 5 | Greedy Algorithms | Quiz 1, Interval Scheduling (SK) | KT 4.1 (Greedy Chapter) Scheduling to maximize profit |
| 6 | Review Session (JC) (Snow Day) |
Review problems Thin Connectivity Notes Thin Connectivity paper |
|
| 7 | Dynamic Programming | Midterm 1 in class (SK) Weighted Interval Scheduling (SK) |
KT 6.1 |
| -- | Spring Break | ||
| 8 | Dynamic Programming | Knapsack (SK) All pairs shortest path (SK) |
KT 6.4 KT 6.8 Floyd-Warshall notes |
| 9 | Dynamic Programming | Sequence Alignment (JC) Matchings (JC) |
KT 6.6 Hall's Theorem proof Matching notes, plus alternative proof of Hall's Theorem |
| 10 | Review Session (SK) Midterm 2 in class (SK, JC) |
||
| 11 | Network Flows | Intro to network flows (SK, JC) | Network Flow slides by Kevin Wayne |
| 12 | Network Flows | Flow algs and scheduling (SK) | Periodic scheduling notes |
| 13 | NP-completeness | NP complete notes | |
| 14 | NP-completeness | Clique is NP-complete Subset Sum is NP-complete Notes on NP-completeness of Vertex Cover |
|
| 15 | Special Topics |