Lecture Topics (tentative)

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

Reading: §1.1

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

Reading: §1.1

---

1/28 — Greedy algorithms I: Interval Scheduling

Reading: §4.1

1/31 — Greedy algorithms II: Minimum Spanning Tree

Reading: §4.5

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

Reading: §4.8

---

2/4 — Class Cancelled (Snow day)

---

2/7 — Dynamic programming I: Weighted Interval Scheduling

Reading: §6.1

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

Reading: §6.4

2/11 — Dynamic programming III: RNA Secondary Structure

Reading: §6.5

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

Reading: §6.8

---

2/16 — Divide and Conquer I: Multiplying Integers

Reading: §5.5

2/18 — Divide and Conquer II: Counting Inversions

Reading: §5.3

2/21 — Review for Prelim 1

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

Reading: §5.4

---

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

Reading: §7.1

2/28 — No class; February break

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

Reading: §7.2

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

Reading: § 7.2

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

Reading: §7.5

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

Reading: §7.5, 7.6

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

Reading: §7.11

---

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

Reading: §8.1, 8.3

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

Reading: §8.2, 8.4

3/18 — NP-Completeness III: Independent Set

Reading: §8.2

3/21 — NP-Completeness IV: Graph Coloring

Reading: §8.7

3/23 — NP-Completeness V: Hamiltonian Cycle, Traveling Salesman

Reading: §8.5

3/25 — NP-Completeness VI: Subset Sum

Reading: §8.8

3/28 — Panorama of Complexity Classes

Reading: §8.9, 8.10

---

3/30 — Computability Theory I: Turing Machine Definitions

Reading: Notes

4/1 — Computability Theory II: Turing Machine Example

Reading: Notes

---

4/4, 4/6, 4/8 — Spring break

---

4/11 — Review for Prelim 2

---

4/13 — Computability Theory III: Universal Turing Machine

Reading: Notes

4/15 — Computability Theory IV: Diagonalization and Undecidability

Reading: Notes

4/18 — Computability Theory V:Reductions and Undecidability

Reading: Notes

4/20 — Computability Theory VI: More Reductions

Reading: Notes

---

4/22 — The Cook-Levin Theorem

Reading: Notes

---

4/25 — Approximation Algorithms I: Greedy algorithms

Reading: §11.1

4/27 — Approximation Algorithms II: Linear programming

Reading: §11.6

4/29 — Approximation Algorithms III: Set Cover

Reading: §11.3

---

5/2 — Randomized Algorithms I: Introduction, Median Finding

Reading: §13.5

5/4 — Randomized Algorithms II: Randomized Quick Sort

Reading: §13.5

5/6 — Randomized Algorithms III: Primality Testing

Reading: Notes

5/9 — Randomized Algorithms IV: Primality Testing

Reading: Notes

---