Lecture Topics (will be updated as the semester progresses)

8/25 — Stable matching I: Gale–Shapley algorithm

Reading: §1.1

8/27 — Stable matching II: Analysis of Gale–Shapley

Reading: §1.1

8/29 — More on Stable Matching, Greedy algorithms I: Interval Scheduling

Reading: §4.1

9/1 — No class (Labor Day)

9/3 — Greedy algorithms I: Interval Scheduling (continued)

Reading: §4.1

9/5 — Greedy algorithms II: Minimum Spanning Tree

Reading: §4.5

9/8 — Dynamic programming I: Weighted Interval Scheduling

Reading: §6.1

9/10 — Dynamic programming II: Subset Sums and Knapsacks

Reading: §6.4

9/12 — Dynamic programming III: Shortest Paths in a Graph

Reading: §6.8

9/15 — Dynamic programming IV: RNA Secondary Structure

Reading: §6.5

9/17 — Divide and Conquer I: Multiplying Integers

Reading: §5.5

9/19 — Divide and Conquer II: Fast Fourier Transform I

Reading: §5.6

9/22 — Divide and Conquer II: Fast Fourier Transform II

Reading: §5.6

9/24 — Divide and Conquer III: Closest Pair of Points in the Plane

Reading: §5.4

9/26 — Network Flow I: Definition and Ford-Fulkerson Algorithm

Reading: §7.1

9/29 — Network Flow II: Max-Flow running time and Cut capacities

Reading: §7.2

10/1 — Review lecture for Prelim 1

Reading:

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

Reading: §7.2

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

Reading: §7.5

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

Reading: §7.5, 7.6

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

Reading: §7.11

10/13 — No Class (Fall Break)

10/15 — NP-Completeness I: Introduction to hardness reductions, P and NP

Reading: §8.1, 8.3

10/17 — NP-Completeness II: NP-complete problems, SAT as an NP-complete problem

Reading: §8.2, 8.4

10/20 — NP-Completeness III: Independent Set

Reading: §8.2

10/22 — NP-Completeness IV: Graph Coloring

Reading: §8.7

10/24 — NP-Completeness V: Hamiltonian Cycle, Traveling Salesman

Reading: §8.5

10/27 — NP-Completeness VI: Subset Sum

Reading: §8.8

10/29 — Panorama of Complexity Classes

Reading: §8.9, 8.10

10/31 — Approximation Algorithms I: Greedy algorithms

Reading: §11.1

11/3 — Approximation Algorithms II: Linear programming

Reading: §11.6

11/5 — Approximation Algorithms III: Set Cover

Reading: §11.3

11/7 — Approximation Algorithms IV: Center Selection

Reading: §11.2

11/10 — Approximation Algorithms V: Knapsack Problem

Reading: §11.8

11/12 — Probability Review for Randomized Algorithms

Reading: Lecture notes

11/14 — Randomized Algorithms I: Minimum Cut

Reading: §13.2

11/17 — Review for Prelim 2


11/19 — Randomized Algorithms III: Max 3-SAT

Reading: §13.4

11/21 — Randomized Algorithms IV: Hashing

Reading: §13.6

11/24 — Randomized Algorithms V: More on Hashing

Reading: §13.6, Notes

12/1 — Computability Theory I: Turing Machines

Reading: Notes

12/3 — Computability Theory II: Turing machine Example

Reading: Notes

12/5 — Computability Theory II: Universal Turing Machine

Reading: Notes

12/8 — Computability IV: Diagonalization and the Halting Problem

Reading: Notes