| 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 |
Breadth-first search, shortest paths
|
Demos for BFS, Dijkstra's
|
|
| Mar 24 |
Bellman-Ford, all-pairs shortest paths
|
PS8 due
PS9 out
|
|
| Mar 28 |
Midterm 2
|
||
| Mar 31 |
Network flow, maximum flows and minimum cuts
|
||
| Apr 4 |
Edmonds-Karp
|
||
| 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 |