Week  Topic  Subtopic  Reading 

1  Introduction to Algorithms  Stable Marriage (SK, JC) Intro to graphs (JC) 
KT 1.1 Manoptimality proof 
2  Graphs: connectivity  BFS, DFS (JC) 2edge connectivity (JC) 
KT 3.23.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 FloydWarshall 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  NPcompleteness  NP complete notes  
14  NPcompleteness  Clique is NPcomplete Subset Sum is NPcomplete Notes on NPcompleteness of Vertex Cover 

15  Special Topics 