Schedule

   
Date Lecture Reading Exercises
Jan 17 Divide-and-conquer; linear-time selection 4, 9.3  
Jan 22 Probabilistic analysis and randomized algorithms 5, 7 1 out
Jan 24 The tails of the binomial distribution C.5  
Jan 29 Hashing 11  
Jan 31 Dynamic programming 15 1 solutions
Feb 5 Greedy algorithms 16 2 out
Feb 7 Minimum spanning trees 23  
Feb 12 Amortized analysis 17  
Feb 14 Review   2 solutions
Feb 19 TEST 1    
Feb 21 Splay trees    
Feb 26 Augmenting data structures 14 3 out
Feb 28 van Emde Boas trees 20  
Mar 5 Data structures for disjoint sets 21  
Mar 7 Elementary graph algorithms 22 3 solutions, 4 out
Mar 12 SPRING BREAK    
Mar 14 SPRING BREAK    
Mar 19 Shortest paths 24, 25  
Mar 21 Maximum flow 26  
Mar 26 Review   4 solutions
Mar 28 TEST 2    
Apr 2 Maximum flow 26  
Apr 4 Maximum flow 26 5 out
Apr 9 Bipartite matching    
Apr 11 Linear programming 29  
Apr 16 NP-completeness 34 5 solutions
Apr 18 NP-completeness 34 6 out
Apr 23 Approximation algorithms 35  
Apr 25 Approximation algorithms 35  
Apr 30 Review   6 solutions
May 2 TEST 3