Syllabus
Readings refer to the course text: Kleinberg and Tardos, Algorithm Design, Addison Wesley/Pearson, 2005. ISBN 0-321-29535-8.
Lecture topics are subject to change.
| DATE | LECTURE/EVENT | NOTES/READINGS |
|---|---|---|
| 1/21 | Welcome and introduction | 1.2 |
| 1/23 | The stable matching problem | 1.1 |
| 1/25 | Greedy algorithms I: Interval scheduling and the “greedy stays ahead” analysis technique | 4.1 |
| 1/28 | Greedy algorithms II: Scheduling to minimize lateness and the “exchange argument” analysis technique | 4.2, 4.3 |
| 1/30 | Greedy algorithms III: Minimum spanning tree algorithms | 4.5 |
| 1/31 | Homework 1 due | |
| 2/1 | Greedy algorithms IV: Data structures for fast minimum spanning tree implementations | 4.6 |
| 2/4 | Dynamic programming I: Weighted interval scheduling | 6.1–6.3 |
| 2/6 | Dynamic programming II: Edit distance, aka sequence alignment | 6.6 |
| 2/8 | Dynamic Programming III: Bellman-Ford shortest path algorithm | 6.8 |
| 2/10 | Homework 2 due | |
| 2/11 | Divide-and-conquer I: Closest pair of points in the plane | 5.4 |
| 2/13 | Divide-and-conquer II: Fast multiplication of integers and matrices | 5.5 |
| 2/15 | Divide-and-conquer III: Fast Fourier transform, polynomial multiplication | 5.6 |
| 2/18 | Dynamic programming IV: RNA secondary structure | 6.5 |
| 2/20 | Prelim 1 review | Review sheet |
| 2/21 | Prelim 1, 7:30–9pm, Uris G01 | |
| 2/22 | Network Flow I: Basic definitions | 7.1 |
| 2/24 | Homework 3 due | |
| 2/25 | Network Flow II: The Ford-Fulkerson Algorithm | 7.1 |
| 2/27 | Network Flow III: Max-Flow Min-Cut, Bipartite Matching | 7.2, 7.5 |
| 3/1 | Network Flow IV: Further examples of flow reductions | 7.10–7.12 |
| 3/4 | Network Flow V: Extensions to network flow | 7.7–7.9 |
| 3/6 | Network Flow VI: Polynomial-time max-flow algorithms | 7.3, Notes on the Edmonds-Karp algorithm, Notes on Dinic's algorithm |
| 3/7 | Homework 4 due | |
| 3/8 | NP-Completeness I: Reductions between SAT and Clique | 8.2, Notes on reductions and NP-completeness |
| 3/11 | NP-Completeness II: Formal Definition of the Class NP. More NP-Complete Problems in Graph Theory | 8.1, 8.3 |
| 3/13 | NP-Completeness III: Covering problems. Set Cover, Exact Cover, Three-Dimensional Matching | 8.6 |
| 3/15 | NP-Completeness IV: Colorability | 8.7 |
| 3/18–22 | Spring Break | |
| 3/25 | NP-Completeness V: Hamiltonian Cycle | 8.5 |
| 3/26 | Homework 5 due | |
| 3/27 | NP-Completeness VI: NP-complete numerical problems. Subset sum, Partition, Knapsack | 8.8 |
| 3/29 | Review of NP-completeness, discussion of other complexity classes. (L, #P, PSPACE) | 8.10 |
| 4/1 | Turing machine definitions | Notes on TMs, §1,2 |
| 4/3 | Turing machine examples. Multitape Turing machines | Notes on TMs, §2,3 |
| 4/5 | Universal Turing machine | Notes on TMs, §4 |
| 4/7 | Homework 6 due | |
| 4/8 | Prelim 2 review | Review sheet |
| 4/9 | Prelim 2, 7:30–9pm, Kimball B11 (aab227–jdb387), Olin 155 (jdh339–sra57), Olin 165 (ss2249–zp34) | |
| 4/10 | Diagonalization and undecidability | Notes on TMs, §4 |
| 4/12 | Decidable and undecidable problems | Notes on TMs, §5,6 |
| 4/15 | The Cook-Levin Theorem | Notes on the Cook-Levin theorem |
| 4/17 | Greedy approximation algorithms: load balancing | 11.1 |
| 4/19 | Greedy approximation algorithms: center selection | 11.2 |
| 4/21 | Homework 7 due | |
| 4/22 | Greedy approximation algorithms: set cover | 11.3 |
| 4/24 | Approximation algorithms via rounding and dynamic programming: the knapsack problem | 11.8 |
| 4/26 | Randomized algorithms I: Randomized algorithms, linearity of expectation, waiting times for independent trials | 13.1, 13.3 |
| 4/29 | Randomized algorithms II: k-th element, quicksort, 3SAT | 13.4, 13.5 |
| 5/1 | Randomized algorithms III: Universal hashing | 13.6 |
| 5/3 | No lecture — slope day | |
| 5/5 | Homework 8 due | |
| 5/12 | Final exam review, 4–6pm, Upson B17 | |
| 5/16 | Final Exam, 9–11:30am (exam period Q), Statler Hall 185 (Statler Auditorium) |