Schedule
All information on this page is subject to change.
Permanent Zoom link: https://cornell.zoom.us/j/93585746762?pwd=TTJTNUY0b21IbUM0bVJDUnBMcC9BQT09
Legend: 
handouts 
slides 
code 
video
| DATE | LECTURE/EVENT | LINKS | |
|---|---|---|---|
| Basic Algorithms | |||
| 8/22 | Welcome and introduction; O(n) median and selection | |
|
| 8/24 | DFS; BFS; connected and strongly connected components |
|
|
| 8/26 | Topological sort; transitive closure; shortest paths |
|
|
| 8/29 | All-pairs shortest paths; Kleene algebra | |
|
| Greedy algorithms | |||
| 8/31 | Minimum spanning trees; blue–red rules | |
|
| 9/2 | Matroids and matroid duality |
|
|
| 9/5 | Labor day – no class | ||
| 9/6 | Last day to add/change credits | ||
| Advanced data structures | |||
| 9/7 | Homework 1 due | ||
| 9/7 | Binomial heaps | |
|
| 9/9 | Fibonacci heaps | |
|
| 9/12 | |||
| 9/14 | |
||
| 9/16 | Random treaps | |
|
| Flow and matching | |||
| 9/19 | Flow definitions | |
|
| 9/21 | Homework 2 due | ||
| 9/21 | Max-flow min-cut theorem | |
|
| 9/23 | Edmonds–Karp algorithm | |
|
| 9/26 | Dinic and MPM algorithms | |
|
| 9/28 | Bipartite matching; weighted matching | |
|
| 9/30 | Matching algorithms | |
|
| Algebraic algorithms | |||
| 10/3 | Fast Fourier transform | |
|
| 10/5 | Homework 3 due | ||
| Parallel algorithms | |||
| 10/5 | PRAMS and uniform circuit families; NC | |
|
| 10/7 | Gray code; hypercube implementation of parallel prefix | |
|
| 10/8–10/11 | Fall break | ||
| 10/12 | Arithmetic; linear recurrences; characteristic polynomials | |
|
| 10/14 | Matrix inversion; matrix rank |
|
|
| 10/15–10/26 | Prelim exam period | ||
| 10/17 | Last day to drop/change grading basis | ||
| 10/17 | Linear equations; Polynomial GCDs | |
|
| 10/19 | Chinese remainder theorem; RSA |
|
|
| Reductions and NP-completeness | |||
| 10/21 | NP; reductions; satisfiability | |
|
| 10/24 | Clique; independent set; vertex cover | |
|
| 10/26 | Colorability; planar colorability; Hamiltonian circuit | |
|
| 10/28 | Knapsack; bin packing | |
|
| 10/31 | Exact cover by 3-sets; 3-dimensional matching; NP-completeness of SAT | |
|
| 11/2 | Homework 4 due | ||
| 11/2 | Cook/Levin theorem |
|
|
| 11/4 | No class; Hartmanis event | ||
| Randomized algorithms | |||
| 11/7 | Luby's algorithm | |
|
| 11/9 | Analysis of Luby's algorithm | |
11/11 | Derandomization | |
| 11/14 | Polynomial testing; tail bounds |
|
|
| 11/16 | Homework 5 due | ||
| Approximation algorithms | |||
| 11/16 | Set cover | |
|
| 11/18 | Bin packing | |
|
| 11/21 | Steiner tree; metric TSP |
|
|
| 11/23–11/27 | Thanksgiving recess | ||
| LP Approximation | |||
| 11/28 | Linear programming; duality; weighted vertex cover | |
|
| 11/30 | Weighted set cover via LP dual fitting | |
|
| 12/2 | LP with randomized rounding |
|
|
| 12/5 | Homework 6 due | ||
| 12/5 | Strong LP duality | |
|
| Final exam period | |||