Week  Topic  Subtopic  Reading 

1  Introduction to Algorithms  Stable Marriage (SK, JC)  KT 1.1 Manoptimality proof 
2  Graphs  Intro to Graphs, BFS (JC) DFS (JC) Strong connectivity (SK) 
KT 3.13.4 CLRS on SC 
3  Graphs  Euler tours (JC) MSTs (JC) SingleSource Shortest Paths (JC)  KT 4.44.6 
4  Graphs  BellmanFord for SSSP (SK) 2edge connectivity/bridge identification (SK,JC) Matchings (SK) 
Notes on bridge ID Notes on matchings (pages 3940) 
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) FloydWarshall's algorithm (SK) 
KT 5.5, 6.1 CLRS on FloydWarshall 
  Spring Break  
9  Dynamic Programming  FloydWarshall (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  NPcompleteness  Intro to NPcompleteness (SK) Reduction: 3CNFSAT to CLIQUE (JC) 
KT 8.48.8 NPC cartoon CLRS on SAT to CLIQUE 
14  NPcompleteness  Reductions, transitivity of reductions (JC) Reductions, finding an optimal VC (JC) (No lecture 5/3) 
Finding an optimal VC via decision oracle 
15  NPcompleteness  Reductions, approaches to intractable problems (SK) Final review on 5/10 (JC) 
CLRS on SAT to SUBSETSUM 