| Date |
Topics |
Old Notes |
Deadlines |
| Thu Aug 25
| Introduction, history, and administrivia
|
| Tue Aug 29
| Recursion
|
| Thu Aug 31
| Divide and conquer
|
| Homework 0 due Fri Sep 1
(Notes on solving recurrences)
|
| Tue Sep 5
| *Fast Fourier transforms
| SH
|
| Thu Sep 7
| Dynamic programming
(including a warning to avoid *greedy algorithms)
|
SH1,
SH2
|
| Tue Sep 12
| Homework 1 due
|
| Thu Sep 14
| Randomization: nuts and bolts
|
SH1,
SH2
|
| Tue Sep 19
| Nuts and bolts continued;
treaps and *skip lists
| SH
| Homework 2 due
|
| Thu Sep 21
| Uniform and universal hashing
| SH
|
| Tue Sep 26
| Midterm 1 — 7:00pm-9:00pm — no lecture
|
| Thu Sep 28
| Amortized analysis: binary counters
|
| Tue Oct 3
| Scapegoat trees and splay trees
|
| Homework 3 due Wed Oct 3
|
| Thu Oct 5
| Maintaining disjoint sets ("union-find")
| SH
|
| Tue Oct 10
| *Path compression has amortized cost O(α(n))
(See also the 2005 paper by Seidel and Sharir)
| SH
| Homework 4 due
|
| Thu Oct 12
| Representing and traversing graphs
|
| Fri Oct 13
|
Drop deadline
|
| Tue Oct 17
| Minimum spanning trees
(The fast version of Kruskal's algorithm uses *Fibonacci heaps.)
|
| Thu Oct 19
| Single-source shortest paths
|
|
| Tue Oct 24
| All-pairs shortest paths
|
| Homework 5 due
|
| Thu Oct 26
| Maximum flows, minimum cuts
| SH
|
| Tue Oct 31
| Midterm 2 — 7:00pm-9:00pm — no lecture
|
| Thu Nov 2
| Maximum flow algorithms and applications
(See also *randomized minimum cuts)
| SH1, SH2
|
| Tue Nov 7
| String matching: Brute force, fingerprints
(See also *number-theoretic algorithms for "probable primes")
|
| Homework 6 due Wed Nov 8
|
| Thu Nov 9
| String matching: Knuth-Morris-Pratt
|
| never
| *Computational geometry:
convex hulls,
line segment intersection,
and
polygon triangulation
|
| Tue Nov 14
| Lower bounds: information theory
|
|
|
| Thu Nov 16
| Lower bounds: adversary arguments
|
| Homework 7 due Fri Nov 17
|
Tue Nov 21
Thu Nov 23
| Thanksgiving break — no lectures
|
| Tue Nov 28
| P, NP, and NP-hard; circuit and formula satisfiability
|
| Thu Nov 30
| Proving NP-hardness via reductions
(See also *lower bounds via reductions)
|
| Tue Dec 5
| Even more NP-hard problems
(See also *approximation algorithms)
|
| Homework 8 due Wed Dec 6
|
| never
| *Linear programming:
definitions and duality, and
the simplex algorithm
|
| Thu Dec 7
| Any questions?
|
| Fri Dec 15
| Final Exam — 1:30-4:30pm
|
