| Date | Topics and deadlines |
|---|---|
| Thu Aug 25 | Introduction, history, and adminsitrivia |
| Tue Aug 30 | NP-completeness [Erin Chambers] |
| Thu Sep 1 | NP-completeness [Erin Chambers]
Homework 0 due, 12:30pm CDT (solutions) |
| Tue Sep 6 | Recursion: subset sum, longest increasing subsequence, optimal binary search trees |
| Thu Sep 6 | Recursion: 3SAT in O(1.7693n) time, maximum independent set in O(1.4423n) time. |
| Tue Sep 13 | Dynamic programming: Fibonacci numbers, longest increasing subsequence, optimal binary search trees
Homework 1 due, 11:59pm CDT (solutions) |
| Thu Sep 15 | More dynamic programming: edit distance, longest common subsequence, saving space, exploiting sparseness |
| Thu Sep 15 | Greedy algorithms: tape sorting, scheduling, Huffman codes |
| Thu Sep 22 | Lempel-Ziv and Burrows-Wheeler data compression (no notes)
Homework 2 due, 11:59pm CDT (solutions) |
| Tue Sep 27 | Midterm 1 (solutions), 7:00pm-8:30pm — no lecture |
| Thu Sep 29 | Greedy approximation algorithms: load balancing, vertex cover |
| Tue Oct 4 | More approximation algorithms: traveling salesman (good and bad) |
| Thu Oct 6 | Polynomial-time approximation schemes: k-center clustering, Subset Sum (no notes) |
| Tue Oct 11 | Randomized algorithms: Sorting nuts and bolts |
| Thu Oct 13 | Randomized treaps and skip lists |
| Tue Oct 18 | Chernoff bounds: If X is the sum of indepedent 0/1 variables and μ=E[X], then Pr[X > (1+δ)μ] < (eδ / (1+δ)1+δ)μ
Homework 3 due, 11:59pm CDT (solutions) |
| Thu Oct 20 | Balls and bins; perfect hashing; universal hashing |
| Tue Oct 18 | Amplification: randomized minimum cut |
| Thu Oct 27 | Randomized incremental Voronoi diagrams (no notes)
Homework 4 due, 11:59pm CDT (solutions) |
| Tue Nov 1 | Midterm 2 (solutions), 7:00pm-8:30pm — no lecture |
| Thu Nov 3 | Review of basic graph algorithms: representations, traversal, minimum spanning trees |
| Tue Nov 8 | Review of basic graph algorithms: single-source and all-pairs shortest paths |
| Thu Nov 10 | Maximum flows and minimum cuts |
| Tue Nov 15 | Max-flow algorithms (Ford-Fulkerson, Edmonds-Karp), matchings, edge-disjoint paths |
| Thu Nov 17 | Max-weight matchings in bipartite graphs, maximum mathings in
general graphs (no notes)
Homework 5 due, 11:59pm CST |
| Tue Nov 22
Thu Nov 24 | Thanksgiving break |
| Tue Nov 29 | Linear programming: Definitions, examples, geometry, duality |
| Thu Dec 1 | Linear programming: Motivation of duality, proof of strong duality theorem |
| Tue Dec 6 | Simplex algorithm (falling marbles and rising bubbles); Seidel's randomized algorithm |
| Thu Dec 8 | Any questions? |
| Tue Dec 13 | Final Exam, 7:00pm-10:00pm, DCL 1310 (the usual lecture room) |