

Date 
Lecture 
Reading 
Exercises 
Jan 15 
Divideandconquer; lineartime 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 
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 

