This schedule will be updated periodically throughout the term. Last update: May 11
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
| Mondays | Wednesdays | Fridays | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Date | Topics | Reading | Date | Topics | Reading | Date | Topics | Reading | ||
| Jan 22 | General Course Info; Stable Matching | Chapter 1: Introduction | Jan 24 | Some Representative Problems | Review Chapters 2 & 3: Basics of Algorithm Analysis & Graphs |
Jan 26 | Divide & Conquer (MergeSort; Integer Multiplication) | Chapter 5 (exclude 5.6): Divide and Conquer | ||
| Jan 29 | Divide & Conquer (Closest Pair) | Jan 31 | Divide & Conquer (Selection) | Feb 2 | Dynamic Programming (Matrix Chain Multiplication) | Chapter 6 (exclude 6.5, 6.7, and 6.10) Dynamic Programming |
||||
| Feb 5 | Dynamic Programming (Min Wt Polygon Triangulation) | Feb 7 | Dynamic Programming (Protein Sequence Alignment) | Feb 9 | Greedy Algorithms (Interval Scheduling; staying ahead vs. exchange arguments) | Chapter 4 (exclude 4.7 - 4.9): Greedy Algorithms | ||||
| Feb 12 | Greedy Algorithms (Minimum Spanning Trees; Kruskal's vs. Prim's Algorithm) | Feb 14 | Greedy Algorithms (Union/Find motivated by Kruskal's MST Algorithm) | Feb 16 | Greedy Algorithms | |||||
| Feb 19 | Dynamic Programming (Shortest Paths with Negative Cycles; Distance Vector Protocols) | 6.9 | Feb 21 | Review for Prelim I (Thursday, Feb 22 at 7:30pm in Upson B17) | Feb 23 | Network Flow | Chapter 7 (exclude 7.4, 7.11, 7.12, and 7.13): Network Flow | |||
| Feb 26 | Network Flow (Ford-Fulkerson Algorithm; Bipartite Matching) | Feb 28 | Network Flow (Max Flow vs. Min Cut) | Mar 2 | Network Flow (Image Segmentation) | |||||
| Mar 5 | Network Flow (Airline Scheduling) | Mar 7 | Network Flow (Protein Sequence Design) | Mar 9 | NP & Computational Intractability | Chapter 8: NP and Computational Intractability | ||||
| Mar 12 | Polynomial Time Reductions (3-SAT; Independent Set; Vertex Cover; Set Cover) | Mar 14 | NP-Completeness (Certifiers) | Mar 16 | NP-Completeness (Circuit SAT) | |||||
| Mar 19 | Spring Break | Spring Break | Spring Break | |||||||
| Mar 26 | NP-Completeness (Graph Coloring) | Mar 28 | NP-Completeness (Hamiltonian Cycle; TSP) | Mar 30 | Finish NP-Completeness (Subset Sum) | |||||
| Apr 2 | Co-NP 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; Independent Set on Trees) | Chapter 10 (exclude 10.3, 10.4, and 10.5): Extending the Limits of Tractability | Apr 6 | Overview of NP-Completeness | |||
| Apr 9 | Review for Prelim II (Tuesday, Apr 10 at 7:30pm in Hollister B14) | Apr 11 | Lecture cancelled (due to illness) | Apr 13 | Approximation Algorithms (Load Balancing = Min Makespan) |
Chapter 11 (only 11.1, 11.2, 11.3, 11.6, and 11.8): Approximation Algorithms | ||||
| Apr 16 | Approximation Algorithms (Center Selection) | Apr 18 | Approximation Algorithms (Use of Linear Programming) | Apr 20 | Approximation Algorithms (Knapsack) | |||||
| Apr 23 | Randomized Algorithms (Max 3-SAT; Review of expectation) | Chapter 13 (13.1 through 13.5, and 13.7): Randomized Algorithms | Apr 25 | Randomized Algorithms (Contention Resolution) | Apr 27 | Randomized Algorithms (Global Min Cut) | ||||
| Apr 30 | Randomized Algorithms (Backwards analysis for Closest Pair of Points) | May 2 | Randomized Algorithms (Selection); Algorithms that Run Forever (Packet Switching Networks) |
Epilogue: Algorithms that Run Forever | May 4 | Last Day (Review; What I Do) | ||||
Our Final Exam is scheduled for Thu, May 17, 9:00 - 11:30 am, in Hollister B14.