This schedule will be updated periodically throughout the term. Last update: May 5.
Readings and, in some cases, web-links are given for each of the topics listed below. Readings are from the course text unless otherwise noted.
Text: Algorithm Design by Jon Kleinberg and Eva Tardos, available at the Campus Store
Other Editions: Previous editions of the text should be OK to use, but be aware that the numbering of the chapters has changed (in particular, Chapters 2 and 3 were in an appendix in earlier versions) and some of the exercises have different numbers.
| Mondays | Wednesdays | Fridays | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Date | Topics | Reading | Date | Topics | Reading | Date | Topics | Reading | ||
| Jan 24 | General Course Info; Stable Matching | Chapter 1: Introduction | Jan 26 | Some Representative Problems | Review Chapters 2 & 3: Basics of Algorithms Analysis & Graphs |
Jan 28 | Greedy Algorithms (Interval Scheduling) | Chapter 4 (exclude 4.7 - 4.9): Greedy Algorithms | ||
| Jan 31 | Greedy Algorithms (Min Spanning Trees) | Feb 2 | Greedy Algorithms (Prim's Algorithm) | Feb 4 | Greedy Algorithms (Kruskal's Algorithm); Union/Find | |||||
| Feb 7 | Dijkstra's Algorithm; Divide & Conquer (MergeSort) | Chapter 5 (exclude 5.6): Divide and Conquer | Feb 9 | Divide & Conquer (Integer Multiplication) | Feb11 | Dynamic Programming (Matrix Chain Multiplication) | Chapter 6 (exclude 6.5, 6.7, and 6.10) Dynamic Programming |
|||
| Feb 14 | Dynamic Programming (Sequence Alignment) | Feb 16 | Divide & Conquer (Closest Pair of Points) | Feb 18 | Dynamic Programming (Shortest Paths in a Graph with Negative Edge Costs) | |||||
| Feb 21 | Dynamic Programming (Segmented Least Squares) | Feb 23 | Review for Prelim I (Thursday, Feb 24 at 7:30PM) | Feb 25 | Network Flow | Chapter 7 (exclude 7.4, 7.11, 7.12, and 7.13): Network Flow | ||||
| Feb 28 | Network Flow (Bipartite Matching) | Mar 2 | Network Flow (Optimality) | Mar 4 | Network Flow (Airline Scheduling) | |||||
| Mar 7 | Network Flow (Image Segmentation) | Mar 9 | Network Flow (Protein Modeling) | Mar 11 | NP & Computational Intractability | Chapter 8: NP and Computational Intractability | ||||
| Mar 14 | NP-Completeness (Vertex Cover; Set Cover) | Mar 16 | NP-Completeness (3-SAT, Independent Set) | Mar 18 | NP-Completeness (Circuit SAT) | |||||
| Mar 21 | Spring Break | Mar 23 | Spring Break | Mar 25 | Spring Break | |||||
| Mar 28 | NP-Completeness (TSP, Hamiltonian Cycle) | Mar 30 | NP-Completeness (3D Matching, Graph Coloring) | Apr 1 | PSPACE: A Class of Problems Beyond NP | Chapter 9 (only 9.1, 9.2, and 9.3): PSPACE: A Class of Problems Beyond NP | ||||
| Apr 4 | Extending the Limits of Tractability (Small Vertex Covers) | Chapter 10 (exclude 10.3, 10.4, and 10.5): Extending the Limits of Tractability | Apr 6 | Extending the Limits of Tractability (Independent Set on Trees) | Apr 8 | Review for Prelim (Some Example Problems from Chapter 8) | ||||
| Apr 11 | Review for Prelim II (Tuesday, Apr 12 at 7:30pm) | Apr 13 | Approximation Algorithms (Load Balancing) |
Chapter 11 (only 11.1, 11.2, 11.6, and 11.8) | Apr 15 | Approximation Algorithms (Center Selection) | ||||
| Apr 18 | Approximation Algorithms (Linear Programming for Approx Vertex Cover) |
Apr 20 | Approximation Algorithms (Arbitrarily Good Approximations for Knapsack) |
Apr 22 | Approximation Algorithms (Finish Knapsack) |
|||||
| Apr 25 | Local Search (Simulate Annealing) |
Chapter 12 (only 12.1 and 12.2) | Apr 27 | Randomized Algorithms (Contention Resolution) |
Chapter 13 (13.1 through 13.5) | Apr 29 | Randomized Algorithms (Global Min Cut; Max 3-SAT) |
|||
| May 2 | Randomized Algorithms (Max 3-SAT; Selection) |
May 4 | Algorithms that Run Forever (Packet Switching Networks) |
Epilogue | May 6 | Last Day (Review; What I Do) |
||||
The Final Exam takes place Friday, May 20 at 9:00AM in Olin 155