Class  Topics  Due 
109 Mon  Administration and introduction. [CLRS, 1] Asymptotic notation. [CLRS, 3] 
PS1 OUT 
111/12 Wed/Thu  Bubblesort [CLRS, Problem 22] Countingsort [CLRS, 8.2] Radixsort [CLRS, 8.3] 

116 Mon  Holiday, no classes  PS1 DUE/ PS2 OUT 
118/19 Wed/Thu  Mergesort [CLRS, 2.3] Quicksort [CLRS, 7] 

123 Mon  Oblivious mergesort [V, 2.1]  PS 2 DUE 
125/26 Wed/Thu  Median [CLRS, 9.3]
Closest pair [CLRS, 33.4] 

130 Mon  Karatsuba's integer multiplication [KT, 5.5]
Strassen's matrix multiplication [CLRS, 4.2] 
QUIZ/ PS3 OUT 
201/02 Wed/Thu  Polynomials and fast Fourier transform [CLRS, 30], [KT, 5.6]  
206 Mon  Introduction to dynamic programming  PS3 DUE 
208/09 Wed/Thu  Practice midterm. Thursday class canceled due to weather.  
213 Mon 
Midterm I
NOTE: Different rooms 11:45am  1:25pm in HT (Hurtig) 129 2:50pm  4:30pm in BK (Behrakis) 310 

215/16 Wed/Thu  Dynamic programming
Subset sum with small numbers Coinchange problem 

220 Mon  Holiday, no classes  PA1 OUT 
222/23 Wed/Thu  Dynamic programming in economics [V, 3.1]
Longest common subsequence [CLRS, 15.4] 
PS4 OUT 
227 Mon  Binary search trees [CLRS 12.1, 12.2] [V 4]
Rotations [CLRS 13.2] [V 4] 

301/02 Wed/Thu  AA Trees [V 4]  PS 4 DUE by Wed 2 PM 
306 Mon  Spring break, no classes  PA1 DUE 
308/09 Wed/Thu  Spring break, no classes  
313 Mon  Hash functions [CLRS 11]  QUIZ 
315/16 Wed/Thu  Review  
320 Mon 
Midterm II
NOTE: Different rooms 11:45am  1:25pm in HT (Hurtig) 129 2:50pm  4:30pm in BK (Behrakis) 310 
PS 5 OUT/ PA2 OUT 
322/23 Wed/Thu  Heaps [CLRS 6]
Graph representations [CLRS 22.1] Breadthfirst search [CLRS 22.2] 

327 Mon  BellmanFord [CLRS 24.1]
Dijkstra [CLRS 24.3] 
PS 5 DUE 
329/30 Wed/Thu  Allpairs shortestpath via matrix multiplication [CLRS 25.1]
Floyd Warshall [CLRS 25.2] Johnson's algorithm [CLRS 25.3] 

403 Mon  3SAT reduces to CLIQUE [CLRS 34.5.1]  QUIZ / PS 6 OUT/ PA2 DUE 
405/06 Wed/Thu 
CLIQUE to VERTEXCOVER [CLRS 34.5.2]
3SAT reduces to SUBSETSUM [CLRS 34.5.5] 3SAT reduces to 3COLOR 

410 Mon 
Flow networks [CLRS 26.1] (our notation is closer to edition 2 CLRS)
FordFulkerson [CLRS 26.2] EdmondsKarp [CLRS 26.3] Maximum bipartite matching [CLRS 26.4] 
PS 6 DUE/ PS 7 OUT 
412/13 Wed/Thu 
The linear programming problem [CLRS 29.1, 29.2]
The simplex algorithm [CLRS 29.3] 2approximation for VERTEXCOVER [CLRS 35.1] 2approximation for weighted VERTEXCOVER [KT 11.6] 

417 Mon  Holiday, no classes  PS 7 DUE 
419/20 Wed/Thu  Review  
426 Wed  Final exam
10:30 am  12:30 pm Science Engineering Complex 102 