Lecture 0 (Sept 26) : Welcome! [Slides] + Background
Lecture 1 (Oct 1) : Graph, Reachability, BFS, DFS [Slides, Annotated]
Lecture 2 (Oct 3) : DFS induced tree, bridges, cut vertices [Cont'd]
Lecture 3 (Oct 8) : connectivity in directed graphs [Cont'd] [Since I have to attend a workshop, the course has been recorded here. The in-person course has been canceled.]
Lecture 4 (Oct 10) : shortest path, heaps [Slides, Annotated]
Lecture 5 (Oct 15) : minimum spanning tree (MST), union-find, other variants [Slides, Annotated] A proof of amortized log*(n) for union-find[Notes]
Lecture 6 (Oct 17) : other greedy algorithms and matroid [Slides, Annotated] A proof for the second MST [Notes]
Lecture 7 (Oct 22) : other greedy algorithms cont'd, binary search + greedy [Slides, Annotated]
Lecture 8 (Oct 24) : binary search cont'd, divide-and-conquer start (count inversion/closest pair) [Slides, Annotated]
Lecture 9 (Oct 29) : divide-and-conquer (faster multiplication/even faster multiplication) FFT [Slides, Annotated]
Lecture 10 (Oct 31) : build data structures from ``useless'' divide-and-conquer -- Segment Tree [Slides, Annotated]
Lecture 11 (Nov 5) : dynamic programming, knapsack problems and variants [Slides, Annotated]
Lecture 12 (Nov 7) : range DP, tree DP [Slides, Annotated]
Lecture 13 (Nov 12) : traveling salesman, the longest increasing subsequence (and speedup), Bellman-Ford and Floyd-Warshall [Cont'd]
Lecture 14 (Nov 14) : randomized algorithm: selection, hash table [Slides, Annotated]
Lecture 15 (Nov 19) : randomized algorithm cont'd; network flow, min-cut max-flow duality [Slides, Annotated]
Lecture 16 (Nov 21) : network flow [Cont'd]
Lecture 17 (Nov 26) : network flow cont'd and NP-complete [Slides]
Lecture 18 (Nov 28) : Skip, Thanksgiving
Lecture 19 (Dec 3) : review [Slides]
Lecture 20 (Dec 5) : basics of computational geometry [Slides, Annotated]
After each class, I will upload annotated notes. The annotated notes may be different from the first version, as we may not have time to cover all materials.