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:
Divide-and-conquer I: Finding the closest pair of points.
-
Reading:
Chapter 5.4.
-
2/8:
-
Lecture:
Divide-and-conquer 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: Linear-space algorithm for edit distance.
-
Reading:
Chapters 6.7.
-
2/19:
-
Lecture:
Dynamic programming IV: Bellman-Ford 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 Ford-Fulkerson algorithm.
-
Reading:
Chapter 7.1.
-
3/3:
-
Lecture:
Network flow II: Analysis of Ford-Fulkerson.
-
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 min-cut 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 NP-completeness.
-
Reading:
Chapter 8.1, 8.3.
-
3/17:
-
Lecture:
NP-complete problems in logic.
-
Reading: Chapter 8.4.
-
3/19:
-
Lecture:
Introduction to designing "gadget reductions".
NP-complete 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:
NP-complete numerical problems.
-
Reading:
Chapter 8.8.
-
4/5:
-
Lecture:
What's harder than NP-complete? 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 Cook-Levin Theorem (SAT is NP-complete).
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:
Polynomial-time 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: