Schedule of Lectures
• 1/19:
• Lecture: Stable matching, part 1.
• Reading: Chapter 1.1; Chapters 2,3.
• 1/21:
• Lecture: Stable matching, part 2.
• 1/23:
• Lecture: Greedy scheduling algorithms
• 1/26:
• Lecture: Minimum spanning tree; Kruskal's algorithm.
• 1/28:
• Lecture: Implementing Kruskal's algorithm using union-find.
• 1/30:
• Lecture: Minimum-cost arborescence
• 2/2:
• Lecture: Introduction to dynamic programming. Weighted interval scheduling.
• Reading: Chapters 6.1, 6.2, 6.3.
• 2/4:
• Lecture: Computing edit distance, a.k.a. sequence alignment.
• 2/6:
• Lecture: Bellman-Ford Shortest Path algorithm.
• 2/9:
• Lecture: RNA secondary structure.
• 2/11:
• Lecture: Divide and conquer algorithms in list processing.
Guest lecturer: Patrick Briest.
• 2/13:
• Lecture: Divide and conquer algorithms in geometry.
Guest lecturer: Jon Kleinberg.
• 2/16:
• Lecture: Divide and conquer algorithms in algebra.
• 2/18:
• Lecture: Review session for prelim 1.
• 2/20:
• Lecture: Divide and conquer algorithms in parallel computing: the carry-lookahead adder.
• 2/23:
• Lecture: Introduction to network flow: basic definitions.
• 2/27:
• Lecture: The Ford-Fulkerson algorithm.
• 3/2:
• Lecture: The max-flow min-cut theorem and the flow integrality theorem. Maximum matching in bipartite graphs.
• 3/4:
• Lecture: Reducing other problems to network flow via bipartite graphs: survey design, baseball elimination.
• 3/6:
• Lecture: Reducing to the min-cut problem: image segmentation.
• 3/9:
• Lecture: Advanced flow reductions: circulations, lower and upper bounds on edges. Application to airline scheduling.
3/23:
• Lecture: Introduction to NP-Completeness. NP-Complete problems in logic and graph theory.
3/25:
• Lecture: CLASS IS CANCELLED
3/27:
• Lecture: Introduction to designing "gadget reductions". More NP-complete graph theoretic problems.
3/30:
• Lecture: The Hamiltonian cycle problem.
4/1:
• Lecture: The 3-dimensional matching problem.
4/3:
• Lecture: NP-complete problems concerning numbers.
4/6:
• Lecture: Review for Prelim 2.
4/8:
• Lecture: Introduction to Turing machines: basic definitions.
• Reading: Handout, Sections 1 and 2.
4/10:
• Lecture: Universal Turing machines
4/13:
• Lecture: Undecidability of the halting problem.
4/15:
• Lecture: Rice's Theorem.
4/17:
• Lecture: Nondeterminism and the Cook-Levin Theorem (SAT is NP-Complete).
4/20:
• Lecture: Introduction to approximation algorithms; greedy approximation algorithm for load balancing.