Date  Topic  Slides  Reading 
September 25  Recap. of basic concepts  Section 2.1 and 2.2  
September 28  Recap. of basic concepts  Section 2.1 and 2.2  
September 30  Introduction  Section 3.1 and 3.2  
October 02  Graph Algorithms  Section 3.1 and 3.2  
October 05  Graph algorithms: BFS  Section 3.1 and 3.2  
October 07  Graph algorithms: BFS application (Bipartite graph)  Section 3.4  
October 09  Graph algorithms: DFS, strongly connected components  Section 3.5  
October 12  Graph algorithms: DAG, Strongly connected components  Section 3.5  
October 14 
Graph algorithms: Strongly connected components Greedy algorithms: Introduction 
Section 3.5 Section 4.1 

October 16  Graph algorithms: Strongly connected components  Section 3.5  
October 19  Greedy algorithms: Interval scheduling  Section 4.1  
October 21  Greedy algorithms: Job scheduling  Section 4.2  
October 23  Midterm 1 (Solution)     
October 26  Greedy algorithms: Job Scheduling, Minimum Spanning Tree  Section 4.5  
October 28  Greedy algorithms: Minimum Spanning Tree  Section 4.5  
October 30  Greedy algorithms: Minimum Spanning Tree, Shortest Path  Section 4.5, 4.4  
November 02 
Greedy algorithms: Shortest path Divide and conquer: Introduction, Merge Sort 
Section 4.4 Section 5.1 

November 04  Divide and conquer: Merge sort, recurrence relations  Section 5.1, 5.2  
November 06  Divide and conquer: Counting inversions  Section 5.3  
November 09  Dynamic Programming: Longest increasing subsequence    
November 11  No class: Veteran’s day     
November 13 
Dynamic Programming: Longest increasing subsequence Longest common subsequence 
  
November 16  Dynamic Programming: Longest common subsequence    
November 18 
Dynamic Programming: Longest common subsequence (memoization) Network Flow: Introduction 
PDF 
 
November 20  Midterm 2 (Solution)     
November 23  Network Flow: FordFulkerson Algorithm  Section 7.1, 7.2  
November 25  Network Flow: FordFulkerson Algorithm  Section 7.1, 7.2  
November 27  No class: Thanksgiving     
November 30  Network Flow: Bipartite matching, Team elimination  Section 7.5, 7.12  
December 02 
Network Flow: Team elimination Computational Intractability: Polynomialtime reduction 
Section 7.12  
December 04  Computational Intractability: Polynomialtime reduction    
December 07  Final (Solution)     