Our textbook is Algorithm Design by Jon Kleinberg and Éva Tardos
Any addition material will be posted here
| Area | Date | Topic | Book | Extra |
|---|---|---|---|---|
| Introduction | Jul 17 | Stable matchings | 1.1 | |
| Graph Algorithms | Jul 18 | DFS and BFS | 3.1-2 | slides |
| Jul 19 | Testing bipartiteness | 3.4 | ||
| Strongly connected components | 3.5 | notes | ||
| Jul 20 | DAGs and topological sort | 3.6 | ||
| Jul 21 | Cut vertices/edges | notes | ||
| Greedy Algorithms | Jul 24 | Interval scheduling | 4.1 | Jul 25 | Minimizing lateness | 4.2 |
| Shortest path | 4.4 | |||
| Jul 26 | Minimum spanning tree | 4.5 | ||
| Union-find data structure | 4.6 | |||
| Jul 27 | Huffman codes | 4.8 | ||
| Jul 28 | Matroids | |||
| Jul 31 | Homework and quiz solving | |||
| Divide and Conquer | Aug 1 | Mergesort and other recurrences | 5.1-2 | |
| Closest pair of points | 5.4 | |||
| Aug 2 | Long integer multiplication | 5.3 | ||
| Fast exponentiation/matrix multiplication | ||||
| Dynamic Programming | Aug 7 | Weighted interval scheduling | 6.1 | |
| Segmented least squares | 6.2 | |||
| Knapsack | 6.4 | |||
| Aug 8 | Shortest paths with negative costs | 6.8 | ||
| Negative cost cycles | 6.9 | |||
| Aug 9 | Sequence alignment in linear space | 6.6-7 | ||
| Maximum flow | Aug 10 | Ford-Fulkerson Algorithm | 7.1 | |
| Max-flow min-cut theorem | 7.2 | |||
| Aug 14 | Baseball elimination | 7.12 | ||
| Aug 15 | Faster max-flow algorithm | 7.3 | ||
| Minimum weight matching | 7.13 | |||
| NP-completeness | Aug 16 | Polynomial-time reductions | 8.1-2 | |
| Aug 17 | NP and NP-complete problems | 8.3-4 | ||
| Directed Hamiltonian cycle | 8.5 | |||
| Aug 18 | Subset Sum | |||
| Aug 21 | co-NP | 8.9 | ||
| PRIME ∈ NP ∩ co-NP | notes | |||
| Aug 22 | Approximation Algorithms | 11.2 |