Date  Topic  Reading  Problem sets 

Jan 10  Introduction, induction 
PS1 out


Jan 13  asymptotic order of growth, Karatsuba 
Karatsuba: Erickson 1.8, demo


Jan 17 
recursion tree, mergesort 
Mergesort: demo


Jan 20  Master theorem, change of variable 
Master theorem:
Erickson Appendix II.3

PS1 due
PS2 out

Jan 24 
deterministic median


Jan 27 
Random variables, quicksort

PS2 due
PS3 out


Jan 31  coin change, dynamic programming 

Feb 3  log cutter, knapsack 
PS3 due
PS4 out


Feb 6  seam carving, typesetting 
Seam carving: paper
Typesetting: MIT video


Feb 10  gerrymander, edit distance 
PS4 due
PS5 out


Feb 14  Midterm 1 

Feb 17  greedy algorithms, files on tape 

Feb 21  interval scheduling 

Feb 24 
Huffman coding

PS5 due
PS6 out


Feb 28  graph, depth first search, topological sort 

Mar 3  Minimum spanning trees, generic algorithm 
PS6 due
PS7 out


Mar 14  Snow day, no class 

Mar 17  Prim, Kruskal 
PS7 due
PS8 out


Mar 21 
Breadthfirst search, shortest paths

Demos for BFS, Dijkstra's


Mar 24 
BellmanFord, allpairs shortest paths

PS8 due
PS9 out


Mar 28 
Midterm 2


Mar 31 
Network flow, maximum flows and minimum cuts


Apr 4 
EdmondsKarp


Apr 7  bipartite matching, image segmentation 
Matching: Erickson 24.3

PS9 due
PS10 out

Apr 11 
Stable matchings


Apr 14  Hashing, fingerprinting 
PS10 due


Apr 18  Fingerprinting, Bloom filter 