Schedule of Lectures

1/24:

Lecture: Welcome and introduction.

Reading:
Chapter 1.2.

1/26:

Lecture: The stable matching problem.

Reading:
Chapter 1.1.

1/28:

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

Reading:
Chapter 4.1.

1/31:

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

Reading:
Chapter 4.2, 4.3.

2/2:

Cornell University closed on account of weather. Class canceled.

2/4:

Lecture:
Greedy algorithms III: Minimum spanning tree algorithms.

Reading:
Chapter 4.5.

2/7:

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

Reading:
Chapter 4.6.

2/9:

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

Reading:
Chapter 5.5.

2/11:

Lecture:
Divideandconquer II: Finding the closest pair of points.
Counting inversions.

Reading:
Chapters 5.3, 5.4.

2/14:

Lecture:
Dynamic programming I: Weighted interval scheduling.

Reading:
Chapters 6.1, 6.2, 6.3.

2/16:

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

Reading:
Chapter 6.6.

2/18:

Lecture:
Shortestpath problems: Dijkstra's algorithm,
introducing the shortestpath problem in graphs
with positive and negative edge costs.

Reading:
Chapter 6.8.

2/21:

Lecture:
Dynamic Programming III: BellmanFord shortest path algorithm.

Reading:
Chapter 6.8.

2/23:

Lecture:
Dynamic programming IV: RNA secondary structure

Reading:
Chapter 6.5.

2/25:

Lecture:
Network Flow I: Introduction, basic definitions, decomposition of flow into
weighted sum of paths and cycles.

Reading:
Chapter 7.1

2/28:

Lecture:
Network Flow II: The FordFulkerson Algorithm.

Reading:
Chapter 7.2

3/2:

Lecture:
Network Flow III: The maxflow mincut theorem, and
correctness of FordFulkerson.

Reading:
Chapter 7.2.

3/4:

3/7:

Cornell University closed on account of weather. Class canceled.

3/9:

Lecture:
Network flow V: Introduction to flow reductions: maximum matching
in bipartite graphs.

Reading:
Chapter 7.5, 7.8.

3/11:

Lecture:
Network flow VI: More flow reductions using bipartite graphs:
baseball elimination.

Reading:
Chapter 7.12.

3/14:

Lecture:
Network flow VII: Reducing to the mincut problem:
minimumcost vertex separator, image segmentation.

Reading:
Chapter 7.10.

3/16:

Lecture:
NPCompleteness I: Reductions between SAT and Vertex Cover.

Reading:
Chapter 8.2.

3/18:

Lecture:
NPCompleteness II: More NPcomplete graphtheoretic
problems. Independent Set, Clique.

Reading:
Chapter 8.2.

3/28:

Lecture:
NPCompleteness III: The complexity class NP, efficient
verifiers, Karp and Turing reductions, definition of
NPcompleteness.

Reading:
Chapters 8.1, 8.3.

3/30:

Lecture:
NPCompleteness IV: NPcomplete partitioning problems.
Exact Cover, 3Coloring.

Reading:
Chapters 8.6, 8.7.

4/1:

Lecture:
NPCompleteness V: NPcomplete numerical problems.
Subset Sum, Knapsack.

Reading:
Chapter 8.8.

4/6:

Lecture:
NPCompleteness VI: NPcomplete sequencing problems.
Hamiltonian Cycle, Traveling Salesman Problem

Reading:
Chapter 8.5.

4/8:

Lecture:
Other complexity classes: L, #P, and PSPACE.

Reading:
None.

4/11:

4/13:

4/15:

4/18:

4/20:

4/22:

Lecture:
Nondeterminism and the CookLevin Theorem.

Reading:
Chapter 8.2.

4/25:

Lecture:
Approximation Algorithms I: The Knapsack Problem.

Reading:
Chapter 11.8.

4/27:

Lecture:
Approximation Algorithms II: Linear Programming and Vertex Cover.

Reading:
Chapter 11.6.

4/29:

Lecture:
Approximation Algorithms III: Greedy Methods.

Reading:
Chapters 11.111.3.

5/2: