| Week | Topic | Subtopic | Reading |
|---|---|---|---|
| 1 | Introduction to Algorithms | Stable Marriage (SK, JC) | KT 1.1 Man-optimality proof |
| 2 | Graphs | Intro to Graphs, BFS (JC) DFS (JC) Strong connectivity (SK) |
KT 3.1-3.4 CLRS on SC |
| 3 | Graphs | Euler tours (JC) MSTs (JC) Single-Source Shortest Paths (JC) | KT 4.4-4.6 |
| 4 | Graphs | Bellman-Ford for SSSP (SK) 2-edge connectivity/bridge identification (SK,JC) Matchings (SK) |
Notes on bridge ID Notes on matchings (pages 39-40) |
| 5 | Greedy Algorithms | Scheduling (JC) Huffman Codes and Data Compression (JC) |
KT 4.1, 4.2, 4.8 Scheduling to maximize profit |
| 6 | Divide and Conquer | Midterm review Midterm 1 Closest Pair (SK) |
KT 5.4 |
| 7 | Divide and Conquer | Closest Pair, cont'd (JC) (Snow day) Tennis problem (SK) |
KT 5.4 |
| 8 | Dynamic Programming | Integer Multiplication (JC) Weighted Interval Scheduling (JC) Floyd-Warshall's algorithm (SK) |
KT 5.5, 6.1 CLRS on Floyd-Warshall |
| -- | Spring Break | ||
| 9 | Dynamic Programming | Floyd-Warshall (JC) Knapsack (JC) NIM games (SK) |
KT 6.4 NIM games |
| 10 | Dynamic Programming | Segmented Least Squares (JC) Sequence Alignment (JC) Midterm review |
KT 6.3 KT 6.6 Alternate proof of Kruskal's alg |
| 11 | Network Flows | Midterm 2 Network Flows (SK) |
|
| 12 | Network Flows | Network Flows (SK, JC) Periodic Scheduling (JC) Baseball Elimination (JC) |
KT 7.1, 7.2, 7.5, 7.12 Periodic Scheduling |
| 13 | NP-completeness | >Intro to NP-completeness (SK) Reduction: 3-CNF-SAT to CLIQUE (JC) |
KT 8.4-8.8 NP-C cartoon CLRS on SAT to CLIQUE |
| 14 | NP-completeness | Reductions, transitivity of reductions (JC) Reductions, finding an optimal VC (JC) (No lecture 5/3) |
Finding an optimal VC via decision oracle |
| 15 | NP-completeness | Reductions, approaches to intractable problems (SK) Final review on 5/10 (JC) |
CLRS on SAT to SUBSETSUM |