Schedule of Lectures

1/25:

Lecture: Welcome and introduction.

Reading: None.

1/27:

Lecture: Greedy algorithms I: Interval scheduling
and the “greedy stays ahead” analysis technique.

Reading:
Chapter 4.1.

1/29:

Lecture: Greedy algorithms II: Scheduling to
minimize lateness and
the “exchange argument” analysis technique.

Reading:
Chapter 4.2, 4.3.

2/1:

Lecture:
Greedy algorithms III: Minimum spanning tree algorithms.

Reading:
Chapter 4.5.

2/3:

Lecture:
Greedy algorithms IV: Data structures for fast
minimum spanning tree implementations.

Reading:
Chapter 4.6.

2/5:

Lecture:
Divideandconquer I: Finding the closest pair of points.

Reading:
Chapter 5.4.

2/8:

Lecture:
Divideandconquer II: Fast multiplication of polynomials and integers.

Reading:
Chapter 5.5.

2/10:

2/12:

Lecture:
Dynamic programming I: Weighted interval scheduling.

Reading:
Chapters 6.1, 6.2, 6.3.

2/15:

Lecture:
Dynamic programming II: Edit distance, a.k.a. sequence alignment.

Reading:
Chapters 6.6.

2/17:

Lecture:
Dynamic programming III: Linearspace algorithm for edit distance.

Reading:
Chapters 6.7.

2/19:

Lecture:
Dynamic programming IV: BellmanFord Shortest Path algorithm.

Reading:
Chapter 6.8.

2/22:

Lecture:
Dynamic programming V: RNA secondary structure.

Reading:
Chapter 6.5.

2/24:

Lecture:
Review for Prelim 1.

Reading:
None.

3/1:

Lecture:
Network flow I: Basic definitions, and the FordFulkerson algorithm.

Reading:
Chapter 7.1.

3/3:

Lecture:
Network flow II: Analysis of FordFulkerson.

Reading:
Chapter 7.3.

3/5:

3/8:

Lecture:
Network flow IV: Introduction to flow reductions: maximum matching
in bipartite graphs, baseball elimination.

Reading:
Chapter 7.5, 7.8, 7.12.

3/10:

Lecture:
Network flow V: Reducing to the mincut problem; image
segmentation.

Reading:
Chapter 7.10.

3/12:

Lecture:
Network flow VI: Advanced flow reductions: circulations, lower
and upper bounds on edges. Application to airline scheduling.

Reading:
Chapter 7.7, 7.9.

REMARK: This lecture was omitted due to
scheduling issues. Students are encouraged
to read the assigned sections of the book.
No problems on the homework or exams will
require this material, but certain
problems may be easier to solve by applying
the material.

3/15:

Lecture:
Introduction to NPcompleteness.

Reading:
Chapter 8.1, 8.3.

3/17:

Lecture:
NPcomplete problems in logic.

Reading: Chapter 8.4.

3/19:

Lecture:
Introduction to designing "gadget reductions".
NPcomplete graph theoretic problems.

Reading:
Chapter 8.2.

3/29:

Lecture:
Hamiltonian Cycle and the Traveling Salesman Problem.

Reading:
Chapter 8.5.

3/31:

Lecture:
Graph coloring.

Reading:
Chapter 8.7.

4/2:

Lecture:
NPcomplete numerical problems.

Reading:
Chapter 8.8.

4/5:

Lecture:
What's harder than NPcomplete? Introduction to Turing machines.

Reading:
Turing machine notes, section 1.

4/7:

4/9: CLASS CANCELLED.

4/12:

4/14:

4/16:

4/19:

Lecture:
Further examples of decidable and undecidable problems.

Reading:
None.

4/21:

Lecture:
Proof of the CookLevin Theorem (SAT is NPcomplete).
Dynamic program for weighted independent set on trees.

Reading:
Chapter 10.2.

4/23:

Lecture:
Introduction to approximation algorithms: greedy algorithms.

Reading:
Chapter 11.1.

4/26:

Lecture:
Greedy approximation algorithms, part 2: the pricing method.

Reading:
Chapter 11.3, 11.4.

4/28:

Lecture:
Linear programming and approximation algorithm design.

Reading:
Chapter 11.6.

4/30:

Lecture:
Polynomialtime approximation schemes.

Reading:
Chapter 11.8.

5/3:

Lecture:
Randomized algorithms I: Karger's minimum cut algorithm.

Reading:
Chapter 13.2. (For review of background material on
probability, see Chapter 13.12.)

5/5:

5/7: