Please keep in mind that this is preliminary
and will change. The chapter numbers are from [CLRS/DPV].
| Day |
Date |
Inst |
Topics Covered |
Notes and Readings |
HWs and Quizes |
| Tue |
Aug 28 |
(CD) |
Lec 1: Intro & Linear time selection
(notes)
(handout on recurrences)
|
[Ch 9/Ch 2.4] |
|
| Thr |
Aug 30 |
(C) |
Lec 2: Concrete Models (notes) |
[Ch 8.1/Ch 2.3] |
Quiz 1: Linear selection, Concrete models |
| Fri |
Aug 31 |
|
Reci 1: Lower and Upper Bounds (worksheet) |
|
HW1 Out: Selection, Concrete, Big-O |
| Tue |
Sep 4 |
(D) |
Lec 3: Amortized Analysis 1 (notes) |
[Ch 17/-] |
|
| Thr |
Sep 6 |
(D) |
Lec 4: Amortized Analysis 2: Splay Trees
(notes)
(Splay tree demo) |
|
Quiz 2: Amortized analysis |
| Fri |
Sep 7 |
|
Reci 2: Amortized Analysis (worksheet) |
|
|
| Sat |
Sep 8 |
|
|
|
HW1 Due. HW2 Out: Amortized analysis, Hashing |
| Tue |
Sep 11 |
(C) |
Lec 5: Hashing 1: Universal Hashing (notes) |
[Ch 11/Ch 1.5] |
|
| Thr |
Sep 13 |
(C) |
Lec 6: Hashing 2: Streaming (Heavy Hitters) (notes) |
|
Quiz 3: Hashing |
| Fri |
Sep 14 |
|
Reci 3: Hashing and Probability Review (worksheet) |
|
|
| Tue |
Sep 18 |
(C) |
Lec 7: Hashing 3: Fingerprinting (notes) |
|
HW2 Orals W-F |
| Thr |
Sep 20 |
(D) |
Lec 8: Dynamic Programming I (notes) |
|
Quiz 4: Hashing + DP |
| Fri |
Sep 21 |
|
Reci 4: Streaming and Hashing (worksheet) |
|
HW3 Out: Hashing, Dynamic Programming |
| Tue |
Sep 25 |
(D) |
Lec 9: Dynamic Programming II (notes) |
[Ch 15, 24.1, 25.1-25.2/Ch 6] |
|
| Thr |
Sep 27 |
(D) |
Lec 10: Network Flow I (notes) |
|
Quiz 5: DP + NF |
| Fri |
Sep 28 |
|
Reci 5: Dynamic Programming (worksheet) |
|
HW3 Due |
| Tue |
Oct 2 |
|
MIDTERM #1 (Selection, Concrete Models, Amortized, Hashing, DP) |
|
|
| Thr |
Oct 4 |
(D) |
Lec 11: Network Flow II (notes) |
[Ch 26/7.2-7.3] |
|
| Fri |
Oct 5 |
|
Reci 6: Network Flow (worksheet) |
|
HW4 Out: Network Flow, Game Theory |
| Tue |
Oct 9 |
(C) |
Lec 12: Game Theory (notes) |
|
|
| Thr |
Oct 11 |
(C) |
Lec 13: Linear Programming I (Basics) (notes) |
[Ch 26/7.2-7.3] |
Quiz 6: Network Flow + LP |
| Fri |
Oct 12 |
|
Reci 7: Linear Programming (worksheet) |
|
|
| Tue |
Oct 16 |
(C) |
Lec 14: Linear Programming II (Simplex & Seidel's) (notes and simplex) |
|
HW4 Orals: T-H |
| Thr |
Oct 18 |
(C) |
Lec 15: Linear Programming III Duality (notes) AND NP-completeness (slides) |
[Ch 26/7.2-7.3] |
Quiz 7: LP |
| Fri |
Oct 19 |
|
NO RECITATION - Mid-semester break |
|
|
| Tue |
Oct 23 |
(D) |
Lec 16: Online Algorithms (notes) |
|
HW5 Out: Linear Programming, Online |
| Thr |
Oct 25 |
(D) |
Lec 17: Multiplicative Weights (notes) |
|
Quiz 8: Online + MW |
| Fri |
Oct 26 |
|
NO RECITATION - President Inauguration Day(worksheet) |
|
|
|
| Tue |
Oct 30 |
(C) |
Lec 18: Approximation Algorithms (notes) |
|
|
| Thr |
Nov 1 |
(D) |
Lec 19: Depth-First-Search and Strong Components (notes) |
[Ch 26/7.2-7.3] |
Quiz 9: NP-completeness + approx |
| Fri |
Nov 2 |
|
Reci 8: Online Algs and Multiplicative Weights (worksheet) |
|
HW5 Due; |
| Tue |
Nov 6 |
|
MIDTERM #2 (Flow, Games, LP, NP, Approx, Online, Multiplicative Weights) |
|
|
| Thr |
Nov 8 |
(D) |
Lec 20: Powerful Arrays (SegTrees, Fenwick Trees) (notes) |
|
HW6 Out: Approx, DFS, Segtrees |
| Fri |
Nov 9 |
|
Reci 9: NP and Approximation algorithms (worksheet) |
|
|
| Tue |
Nov 13 |
(D) |
Lec 21: Computational Geometry I (Convex Hull) (notes) |
|
|
| Thr |
Nov 15 |
(C) |
Lec 22: Computational Geometry II (Sweepline) (notes) |
|
Quiz 10: Segtrees, Comp Geometry |
| Fri |
Nov 16 |
|
Reci 10: Computational Geometry (worksheet) |
|
|
| Tue |
Nov 20 |
(C) |
Lec 23: Computational Geometry III (Closest Pair) (notes) |
|
HW6 Due |
| Thr |
Nov 22 |
|
Thanksgiving - No Class |
|
|
| Fri |
Nov 23 |
|
Thanksgiving - No recitation |
|
|
| Tue |
Nov 27 |
(C) |
Lec 24: Suffix Trees and Arrays (notes) |
|
HW7 Out: Comp Geometry, Suffix Trees |
| Thr |
Nov 29 |
(C) |
Lec 25: BWT and compression (notes) |
|
Quiz 11: Comp Geo, Suffix Trees, BWT |
| Fri |
Nov 30 |
|
Reci 11: String algorithms (worksheet) |
|
|
| Tue |
Dec 4 |
(D) |
Lec 26: Suffix array construction (notes) |
|
|
| Thr |
Dec 6 |
(D) |
Lec 27: Fibonacci Heaps (notes) |
|
Quiz 12: Compression and fib heaps |
| Fri |
Dec 7 |
|
Reci 12: Final Review |
|
HW7 Orals W-F |