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
-
Reading:
Chapter 4.1, 4.2.
-
1/26:
-
Lecture:
Minimum spanning tree; Kruskal's algorithm.
-
Reading:
Chapter 4.5.
-
1/28:
-
Lecture:
Implementing Kruskal's algorithm using union-find.
-
Reading:
Chapter 4.6.
-
1/30:
-
Lecture:
Minimum-cost arborescence
-
Reading:
Chapter 4.9.
-
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.
-
Reading:
Chapters 6.6.
-
2/6:
-
Lecture:
Bellman-Ford Shortest Path algorithm.
-
Reading:
Chapter 6.8.
-
2/9:
-
Lecture:
RNA secondary structure.
-
Reading:
Chapter 6.5.
-
2/11:
-
Lecture:
Divide and conquer algorithms
in list processing.
Guest lecturer: Patrick Briest.
-
Reading:
Chapters 5.3, 13.5.
-
2/13:
-
Lecture:
Divide and conquer algorithms
in geometry.
Guest lecturer: Jon Kleinberg.
-
Reading:
Chapter 5.4.
-
2/16:
-
Lecture:
Divide and conquer algorithms
in algebra.
-
Reading:
Chapters 5.5, 5.6.
-
2/18:
-
Lecture:
Review session for prelim 1.
-
Reading:
Review chapters 1,4,5,6.
-
2/20:
-
Lecture:
Divide and conquer algorithms in parallel computing:
the carry-lookahead adder.
-
Reading:
None.
-
2/23:
-
Lecture:
Introduction to network flow: basic definitions.
-
Reading:
Chapter 7.1.
-
2/27:
-
Lecture:
The Ford-Fulkerson algorithm.
-
Reading:
Chapters 7.1, 7.2.
-
3/2:
-
Lecture:
The max-flow min-cut theorem and the flow integrality theorem.
Maximum matching in bipartite graphs.
-
Reading:
Chapter 7.2,7.5.
-
3/4:
-
Lecture:
Reducing other problems to network flow
via bipartite graphs: survey design,
baseball elimination.
-
Reading:
Chapter 7.8, 7.12.
-
3/6:
-
Lecture:
Reducing to the min-cut problem: image
segmentation.
-
Reading:
Chapter 7.10.
-
3/9:
-
Lecture:
Advanced flow reductions: circulations, lower and
upper bounds on edges. Application to airline
scheduling.
-
Reading:
Chapter 7.7, 7.9.
3/23:
-
Lecture:
Introduction to NP-Completeness.
NP-Complete problems in logic and graph theory.
-
Reading:
Chapter 8.1-8.4.
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.
-
Reading:
Chapter 8.5.
4/1:
-
Lecture:
The 3-dimensional matching problem.
-
Reading:
Chapter 8.6.
4/3:
-
Lecture:
NP-complete problems concerning numbers.
-
Reading:
Chapter 8.8.
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
-
Reading:
Handout, Section 3.
4/13:
-
Lecture:
Undecidability of the halting problem.
-
Reading:
Handout, Sections 4.1-4.4.
4/15:
-
Lecture:
Rice's Theorem.
-
Reading:
Handout, Section 4.5.
4/17:
-
Lecture:
Nondeterminism and the Cook-Levin Theorem (SAT is NP-Complete).
-
Reading:
Handout, Section 5.
4/20:
-
Lecture:
Introduction to approximation algorithms; greedy approximation
algorithm for load balancing.
-
Reading:
Chapter 11.1
4/22:
-
Lecture:
Introduction to linear programming; LP rounding approximation
algorithm for weighted vertex cover.
-
Reading:
Chapter 11.6
4/24:
-
Lecture:
Primal-dual approximation algorithms: vertex cover and set cover.
-
Reading:
Chapter 11.4
4/27:
-
Lecture:
Polynomial-time approximation schemes: the knapsack problem.
-
Reading:
Chapter 11.8
4/29:
-
Lecture:
Randomized algorithms I: Karger's global min-cut algorithm.
-
Reading:
Chapter 13.2
5/1: