Schedule

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