Date 
Notes 
Topics 
Additional References 
01/05/16 
pdf tex 
Basic Graph Theory Concepts, Trees, Cayley's Theorem  Graph Theory slides 
01/12/16 
pdf tex 
Eulerian Circuits and DNA sequencing 
[LPV] Chapters 1 to 5,
DNA Arrays 
01/14/16 
pdf tex 
Minimum Spanning Trees 

01/19/16 
pdf tex 
Network Flows and Maxflow mincut 
[BVR] chapter 5,
MaxFlow

01/21/16 
pdf tex 
Variations of Network Flow Algorithms  
01/26/16 
pdf tex 
Applications of Network Flows I 
MaxFlow/MinCut Applications 
01/30/16 
pdf tex 
Applications of Network Flows II, Global Min cut 

02/02/16 
pdf 
Linear Programming (a quick review) 
[BVR] chapter 3,
chapter 4 
02/04/16 
pdf tex 
MinCost Flow  
02/9/16 
pdf tex 
Marriage, Stability, and Honesty  
02/16/16 
pdf tex 
Intractibility  
02/18/16 
pdf tex 
Approximation Algorithms: Vertex Cover, Job Scheduling  
02/23/16 
pdf
tex 
Approximation Algorithms II: Minimum Vertex Cover, Job Scheduling Revisited  
02/25/16 
pdf
tex 
Approximation Algorithms III: Maximum Satisfiability  
03/8/16 
pdf

TSP Problems  
03/10/16 
pdf

Course Review and Beyond*  