

Date 
Lecture 
Reading 
Exercises 
Jan 17 
Divideandconquer; lineartime 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 
NPcompleteness 
34 
5 solutions 
Apr 18 
NPcompleteness 
34 
6 out 
Apr 23 
Approximation algorithms 
35 

Apr 25 
Approximation algorithms 
35 

Apr 30 
Review 

6 solutions 
May 2 
TEST 3 

