Date  Topic  Slides  Reading 
September 24  Introduction  Chapters 1 and 2  
September 29  Introduction, Graph algorithms  Section 3.1, 3.2, 3.3, 3.4  
October 01  Graph algorithms  Section 3.1, 3.2, 3.3, 3.4, 3.5, 3.6  
October 06  Greedy Algorithms: Interval Scheduling, Fractional Knapsack  Section 4.1  
October 08  Greedy Algorithms: Fractional Knapsack, Job scheduling  Section 4.2  
October 13  Greedy algorithms: Minimum Spanning Tree  Section 4.5, 4.6  
October 15 
Greedy algorithms: Minimum Spanning Tree, Shortest Path Greedy (approximation) algorithms: Set Cover, Minimum Makespan 
Section 4.6, 4.4 Section 11.1, 11.2 

October 20 
Greedy (approximation) algorithms: Minimum Makespan Divide and conquer: Closest pair of points, Median finding 
Section 11.1 Section 5.1, 5.2, 5.3, 5.4. 5.5 

October 22  Divide and conquer: Median finding, Fast Fourier Transform (FFT)  Section 5.6  
October 27 
Divide and conquer: Fast Fourier Transform, Master Theorem Dynamic Programming: Longest increasing subsequence 
Section 5.6  
October 29  Midterm (Solution)     
November 03  Dynamic Programming: Longest increasing subsequence, Longest common subsequence 
PDF 
 
November 05  Dynamic Programming: FloydWarshall, 01 Knapsack, Travelling Salesperson  Section 6.4, 6.8  
November 10  Network Flow: Introduction, FordFulkerson  Section 7.1, 7.2  
November 12  Network Flow: Ford Fulkerson, Scaling Maxflow  Section 7.1, 7.2, 7.3  
November 17  Network Flow: EdmondsKarp, Maximum Matching, Hall’s Theorem  Section 7.5  
November 19 
Network Flow: Team Elimination, Feasible Circulation, Image Segmentation 
Section 7.7, 7.10, 7.12  
November 24 
Network Flow: Edgedisjoint path Computational Intractability: Introduction, Polynomialtime reduction 
Section 7.6 Section 8.1, 8.2 

November 26  No class: Thanksgiving     
December 01  Computational Intractability: Polynomialtime reduction, NP, NPcomplete  Section 8.3, 8.4  
December 03  Computational Intractability: NP, NPcomplete, NPhard  Section 8.4, 8.5, 8.7  
December 10  Final Exam (36pm at CENTR 214)     