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.