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 unionfind.

Reading:
Chapter 4.6.

1/30:

Lecture:
Minimumcost 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:
BellmanFord 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 carrylookahead adder.

Reading:
None.

2/23:

Lecture:
Introduction to network flow: basic definitions.

Reading:
Chapter 7.1.

2/27:

Lecture:
The FordFulkerson algorithm.

Reading:
Chapters 7.1, 7.2.

3/2:

Lecture:
The maxflow mincut 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 mincut 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 NPCompleteness.
NPComplete problems in logic and graph theory.

Reading:
Chapter 8.18.4.
3/25:

Lecture:
CLASS IS CANCELLED
3/27:

Lecture:
Introduction to designing "gadget reductions".
More NPcomplete graph theoretic problems.
3/30:

Lecture:
The Hamiltonian cycle problem.

Reading:
Chapter 8.5.
4/1:

Lecture:
The 3dimensional matching problem.

Reading:
Chapter 8.6.
4/3:

Lecture:
NPcomplete 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.14.4.
4/15:

Lecture:
Rice's Theorem.

Reading:
Handout, Section 4.5.
4/17:

Lecture:
Nondeterminism and the CookLevin Theorem (SAT is NPComplete).

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:
Primaldual approximation algorithms: vertex cover and set cover.

Reading:
Chapter 11.4
4/27:

Lecture:
Polynomialtime approximation schemes: the knapsack problem.

Reading:
Chapter 11.8
4/29:

Lecture:
Randomized algorithms I: Karger's global mincut algorithm.

Reading:
Chapter 13.2
5/1: