Schedule of Lectures

1/21:

Lecture: Stable matching, part 1.

Reading: Chapter 1.1; Chapters 2,3.

1/23:

Lecture: Stable matching, part 2.

1/25:

Lecture:
Greedy scheduling algorithms.

Reading: Chapter 4.1, 4.2.

1/28:

Lecture:
Five representative problems.

Reading:
Chapter 1.2.

1/30:

Lecture:
Minimum spanning tree; Kruskal's algorithm.

Reading:
Chapter 4.5.

2/1:

Lecture:
Implementing Kruskal's algorithm using unionfind.

Reading:
Chapter 4.6.

2/4:

Lecture:
Divide and conquer algoithms: Multiplying polynomials
and integers (Karatsuba's algorithm).

Reading:
Chapter 5.1, 5.2, 5.5.

2/6:

Lecture:
The Fast Fourier Transform

Reading:
Chapter 5.6.

2/8:

Lecture:
Divide and conquer algorithms in computational geometry:
finding the closest pair of points.

Reading:
Chapter 5.4.

2/11:

Guest lecturer: Jon Kleinberg.

Lecture:
Introduction to dynamic programming; weighted interval scheduling.

Reading:
Chapter 6.1.

2/13:

Lecture:
Computing RNA secondary structure.

Reading:
Chapter 6.5.

2/15:

Lecture:
Edit distance.

Reading:
Chapter 6.6.

2/18:

Lecture:
BellmanFord shortest path algorithm.

Reading:
Chapter 6.86.10.

2/20:

Lecture:
Review of dynamic programming.

Reading:
Chapter 6.16.2, 6.56.6, 6.86.10.

2/22:

Lecture:
Introduction to network flow.

Reading:
Chapter 7.1.

2/25:

Lecture:
The FordFulkerson algorithm for maximum flow.

Reading:
Chapter 7.17.3.

2/27:

Lecture:
The maxflow/mincut theorem, flow integrality.

Reading:
Chapter 7.17.3.

2/29:

Lecture:
The preflowpush algorithm for maximum flow.

Reading:
Chapter 7.4.

3/3:

Lecture:
Baseball elimination

Reading:
This lecture is based on Chapter 7.12.
The week's reading is Chapter 7, Sections 5 through 13.

3/5:

Lecture:
Image segmentation

Reading:
Chapter 7.10

3/7:

Lecture:
Maximum matching

Reading:
Chapters 7.5, 7.13.

3/10:

Lecture:
Introduction to NPcompleteness

Reading:
Chapter 8.1

3/12:

Lecture:
Some basic reductions: 3SAT, clique, vertex cover, independent set

Reading:
Chapters 8.1, 8.2.

3/14:

Lecture:
The CookLevin Theorem

Reading:
Chapters 8.3, 8.4.

3/24:

Lecture:
NPcomplete sequencing problems: Hamiltonian cycle.

Reading:
Chapter 8.5

3/26:

Lecture:
NPcomplete sequencing problems: Hamiltonian cycle and path, traveling salesman problem.

Reading:
Chapter 8.5

3/28:

Lecture:
NPcomplete covering and packing problems:
set cover, set packing, independent set in degree3 graphs.

Reading:
Chapter 8.1

3/31:

Lecture:
NPcomplete partitioning problems: 3dimensional matching.
NPcomplete numerical problems: subset sum.

Reading:
Chapters 8.6, 8.8

4/2:

Lecture:
Pseudopolynomial time algorithms. Fixedparameter tractability.

Reading:
Chapter 6.4, Chapter 10.1.

4/4:

Lecture:
Solving NPComplete problems on trees.

Reading:
Chapter 10.2.

4/7:

Lecture:
Review session for Prelim 2.

Reading:
None.

4/9:

Lecture:
Intro to approximation algorithms; greedy approximation
algorithm for load balancing.

Reading:
Chapter 11.1

4/11:

Lecture:
The greedy set cover algorithm.

Reading:
Chapter 11.3

4/14:

Lecture:
The pricing method: weighted vertex cover.

Reading:
Chapter 11.4

4/16:

Lecture:
Introduction to linear programming; LP rounding approximation
algorithm for weighted vertex cover.

Reading:
Chapter 11.6

4/18:

Lecture:
More LP rounding: scheduling on unrelated parallel machines

Reading:
Chapter 11.7

4/21:

Lecture: Randomized algorithms I: Karger's randomized contraction
algorithm for mincut

Reading: Chapter 13.113.2

4/23:

Lecture: Randomized algorithms II: Hashing

Reading: Chapter 13.313.6

4/25:

4/28:

Lecture: Online algorithms I: Caching algorithms

Reading:
Chapter 13.8

4/30:

5/2:

Lecture:
Packet switching

Reading:
Epilogue of KleinbergTardos.