Lecture Topics (tentative)

1/23 — Stable matching I: Gale–Shapley algorithm

Reading: §1.1

1/25 — Stable matching II: Analysis of Gale–Shapley

Reading: §1.1

1/27 — Greedy algorithms I: Interval Scheduling

Reading: §4.1

1/30 — Greedy algorithms II: Minimum Spanning Tree

Reading: §4.5

2/1 — Greedy algorithms III: Huffman Codes and Data Compression

Reading: §4.8

2/3 — Dynamic programming I: Weighted Interval Scheduling

Reading: §6.1

2/6 — Dynamic programming II: Subset Sums and Knapsacks

Reading: §6.4

2/8 — Dynamic programming III: RNA Secondary Structure

Reading: §6.5

2/10 — Dynamic programming IV: Shortest Paths in a Graph

Reading: §6.8

2/13 — Divide and Conquer I: Multiplying Integers

Reading: §5.5

2/15 — Divide and Conquer II: Fast Fourier Transform I

Reading: §5.6

2/17 — Divide and Conquer II: Fast Fourier Transform II

Reading: §5.6

2/20 — Review for Prelim 1

2/22 — Divide and Conquer III: Closest Pair of Points in the Plane

Reading: §5.4

2/24 — Network Flow I: Definition and Ford-Fulkerson Algorithm

Reading: §7.1

2/27 — No class; February break

3/1 — Network Flow II: Network Flow II: Max-Flow running time and Cut capacities

Reading: §7.2

3/3 — Network Flow III: Max-Flow Min-Cut theorem

Reading: § 7.2

3/6 — Network Flow IV: Reductions to Max-flow problem

Reading: §7.5

3/8 — Network Flow V: More on Reductions to Max-flow problem

Reading: §7.5, 7.6

3/10 — Network Flow VI: Applications to Min-Cuts

Reading: §7.11

3/13 — NP-Completeness I: Introduction to hardness reductions, P and NP

Reading: §8.1, 8.3

3/15 — NP-Completeness II: NP-complete problems, SAT as an NP-complete problem

Reading: §8.2, 8.4

3/17 — NP-Completeness III: Independent Set, Vertex Cover, Set Cover

Reading: §8.2

3/20 — NP-Completeness IV: Hamiltonian Cycle, Traveling Salesman

Reading: §8.5

3/22 — NP-Completeness V: Subset Sum

Reading: §8.8

3/24 — Panorama of Complexity Classes

Reading: §8.9, 8.10

3/27 — Approximation Algorithms I: Greedy algorithms

Reading: § 11.1

3/29 — Approximation Algorithms II: Linear Programming

Reading: § 11.6

3/31 — Approximation Algorithms III: Set Cover

Reading: § 11.3

4/3, 4/5, 4/7 — Spring break

4/10 — Approximation Algorithms IV: Center Selection

Reading: § 11.2

4/12 — Approximation Algorithms V: Knapsack Problem

Reading: § 11.8

4/14 — Probability Review for Randomized Algorithms

Reading: lecture notes

4/17 — Review for Prelim 2

4/19 — Randomized Algorithms I: Minimum Cut

Reading: § 13.2

4/21 — Randomized Algorithms II: Median Finding

Reading: § 13.5

4/24 — Randomized Algorithms III: Max 3-SAT

Reading: § 13.4

4/26 — Randomized Algorithms IV: Hashing

Reading: §13.6

4/28 — Randomized Algorithms V: More on Hashing

Reading: 13.6, Notes

5/1 — Computability Theory I: Turing Machines

Reading: Notes

5/3 — Computability II: Turing Machine example

Reading: Notes

5/5 — Universal Turing Machine

Reading: Notes

5/8 — Diagonalization and the Halting Problem

Reading: Reading: Notes