Schedule of Lectures
-
1/23:
-
Lecture: Welcome and introduction.
-
Reading:
Chapter 1.2.
-
1/25:
-
Lecture: The stable matching problem.
-
Reading:
Chapter 1.1.
-
1/27:
-
Lecture: Greedy algorithms I: Interval scheduling
and the “greedy stays ahead” analysis technique.
-
Reading:
Chapter 4.1.
-
1/30:
-
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/6:
-
Lecture:
Dynamic programming I: Weighted interval scheduling.
-
Reading:
Chapters 6.1, 6.2, 6.3.
-
2/8:
-
Lecture:
Dynamic programming II: Edit distance, a.k.a. sequence alignment.
-
Reading:
Chapter 6.6.
-
2/10:
-
Lecture:
Dynamic Programming III: Bellman-Ford shortest path algorithm.
-
Reading:
Chapter 6.8.
-
2/13:
-
2/15:
-
Lecture:
Dynamic programming IV: RNA secondary structure
-
Reading:
Chapter 6.5.
-
2/17:
-
Lecture:
Divide-and-conquer I: Fast multiplication of polynomials, integers, and matrices.
-
Reading:
Chapter 5.5.
-
2/20:
-
Lecture:
Divide-and-conquer II: Closest pair of points in the plane.
-
Reading:
Chapter 5.4.
-
2/22:
-
2/24:
-
Lecture:
Network Flow I: Basic definitions.
-
Reading:
Chapter 7.1.
-
2/27:
-
Lecture:
Network Flow II: The Ford-Fulkerson Algorithm
-
Reading:
Chapter 7.1.
-
2/29:
-
Lecture:
Network Flow III: Max-Flow Min-Cut, Bipartite Matching
-
Reading:
Chapter 7.2, 7.5.
-
3/2:
-
Lecture:
Network Flow IV: Further examples of flow reductions.
-
Reading:
Chapter 7.10-7.12.
-
3/5:
-
Lecture:
Network Flow V: Extensions to network flow.
-
Reading:
Chapter 7.7-7.9.
-
3/7:
-
3/9:
-
Lecture:
NP-Completeness I: Reductions between SAT
and Independent Set.
-
Reading:
Chapter 8.2.
-
3/12:
-
Lecture:
NP-Completeness II: Formal Definition of the Class NP.
More NP-Complete Problems in Graph Theory.
-
Reading:
Chapter 8.1,8.3.
-
3/14:
-
Lecture:
NP-Completeness III:
Three-Dimensional Matching.
-
Reading:
Chapters 8.6.
-
3/16:
-
Lecture:
NP-Completeness IV:
Feedback Edge Set
-
Reading:
Chapter 8.7.
-
3/26:
-
Lecture:
NP-Completeness V:
Hamiltonian Cycle
-
Reading:
Chapter 8.5.
-
3/28:
-
Lecture:
NP-Completeness VI:
NP-complete numerical problems.
Subset sum, Knapsack.
-
Reading:
Chapter 8.8.
-
3/30:
-
Lecture:
Review of NP-completeness, discussion of
other complexity classes. (L, #P, PSPACE)
-
Reading:
Chapter 8.10.
-
4/2:
-
4/4:
-
4/6:
-
4/9:
-
4/11:
-
4/13:
-
4/16:
-
Lecture:
The Cook-Levin Theorem. Approximation algorithms: basic definitions.
-
Reading:
Chapter 11.1.
-
4/18:
-
Lecture:
Greedy approximation algorithms: load balancing, set cover.
-
Reading:
Chapter 11.1, 11.3.
-
4/20:
-
Lecture:
Approximation algorithms via rounding and dynamic programming:
the knapsack problem.
-
Reading:
Chapter 11.8.
-
4/23:
-
Lecture:
Approximation algorithms via linear programming:
vertex cover.
-
Reading:
Chapter 11.6.
-
4/25:
-
4/27:
-
Lecture:
Randomized algorithms II: Global minimum cut.
-
Reading:
Chapter 13.2.
-
4/30:
-
Lecture:
Randomized algorithms III:
Prediction using multiplicative weights.
-
Reading:
Lecture notes.
-
5/2:
Guest lecturer: John Hopcroft.
-
Lecture:
Future directions in algorithmic research.
-
Reading:
None.
-
5/4:
Class is canceled.