CS 224: Advanced Algorithms
[Home]
[Lectures]
[Assignments]
[Project]
Scribing
- Use this template when
scribing.
- Each student may have to scribe 1-2 lectures, depending on class
size.
- Pick a date below when you are available to scribe and send your
choice to
cs224-f14-staff@seas.harvard.edu. First-come first-served.
- Submit scribe notes (pdf + source) to
cs224-f14-staff@seas.harvard.edu.
- Please give real bibliographical citations for the papers that we
mention in class
(DBLP can
help you collect bibliographic info).
- Scribe notes are due by 9pm on the day after lecture. They are posted
immediately without proofreading (though we may proofread later and ask for some changes to be made.)
Scribe Notes
- Tuesday, Sept. 2 — logistics, course topics, word RAM, predecessor, van Emde Boas, y-fast tries.
Scribe: Marcus Schorow.
[PDF][TeX][video]
- Thursday, Sept. 4 — fusion trees, word-level parallelism, most significant set bit in constant time.
Scribe: David Liu.
[PDF][TeX][video]
- Tuesday, Sept. 9 — hashing: load balancing, k-wise independence, chaining, linear probing.
Scribe: Thibaut Horel.
[PDF][TeX][video]
- Thursday, Sept. 11 — symmetrization, hashing: linear probing (5-wise indep.), bloom filters, cuckoo hashing, bloomier filters.
Scribe: Marco Gentili.
[PDF][TeX][video]
- Tuesday, Sept. 16 — hashing: cuckoo hashing analysis, power of two choices.
Scribe: Albert Wu.
[PDF][TeX][video]
- Thursday, Sept. 18 — amortized analysis, binomial heaps, Fibonacci heaps.
Scribe: Eric Balkanski.
[PDF][TeX][FIG][video]
- Tuesday, Sept. 23 — splay trees.
Scribe: Jarosław Błasiok.
[PDF][TeX][BIB][video]
- Thursday, Sept. 25 — online algorithms, competitive analysis, move-to-front, paging.
Scribe: Jean Pouget-Abadie.
[PDF][TeX][video]
- Tuesday, Sept. 30 — randomized paging, packing/covering linear programs, weak duality, approximate complementary slackness, primal/dual online algorithms (2-competitive deterministic ski rental).
Scribe: Yi-Hsiu Chen.
[PDF][TeX][video]
- Thursday, Oct. 2 — online primal/dual: e/(e-1) ski rental, set cover; approximation algorithms via dual fitting: set cover.
Scribe: Zhengyu Wang.
[PDF][TeX][video]
- Tuesday, Oct. 7 — approximation algorithms via dual fitting (wrap-up), LP integrality gaps, definitions of PTAS/FPTAS/FPRAS, PTAS for knapsack.
Scribe: David Ding.
[PDF][TeX][video]
- Thursday, Oct. 9 — FPTAS (knapsack), FPRAS (DNF counting), semidefinite programming, Goemans-Williamson MAXCUT algorithm.
Scribe: Yifan Wu.
[PDF][TeX][video]
- Tuesday, Oct. 14 — topic modeling, nonnegative matrix factorization.
Guest lecture: Rong Ge.
Scribe: Vasileios Nakos.
[PDF][TeX][video]
- Thursday, Oct. 16 — approximate nearest neighbor, locality sensitive hashing.
Guest lecture: Piotr Indyk.
Scribe: Jao-ke Chin-Lee.
[PDF][TeX][slides][no video]
- Tuesday, Oct. 21 — linear programming: standard form, vertices, bases, simplex.
Scribe: Matt Rauen.
[PDF][TeX][FIG][video]
- Thursday, Oct. 23 — simplex wrap-up, strong duality, complementary slackness, ellipsoid, intro to interior point.
Scribe: Colin Lu.
[PDF][TeX][video]
- Tuesday, Oct. 28 — path-following interior point, first order methods (gradient descent).
Scribe: Ben Thompson.
[PDF][TeX][video]
- Thursday, Oct. 30 — second order methods (Newton's method), path-following interior point wrap-up.
Scribe: Xiaoyu He.
[PDF][TeX][video]
- Tuesday, Nov. 4 — learning from experts, multiplicative weights.
Scribe: Calvin Deng.
[PDF][TeX][video]
- Thursday, Nov. 6 — linear programming via multiplicative weights, flows, augmenting paths.
Scribe: David Palmer.
[PDF][TeX][video]
- Tuesday, Nov. 11 — scaling for max flow, blocking flow.
Scribe: Nithin Tumma.
[PDF][TeX][video]
- Thursday, Nov. 13 — preferred path decomposition, link-cut trees.
Scribe: Malcolm Granville.
[PDF][TeX][video]
- Tuesday, Nov. 18 — heavy-light decomposition, O(log2n) amortized analysis of link-cut trees, min cost max flow, min cost circulation, shortest augmenting paths.
Scribe: Jeffrey Yan.
[PDF][TeX][video]
- Thursday, Nov. 20 — more efficient exponential-time algorithms: exponential divide-and-conquer (TSP), pruned brute force (3-SAT), Schöning's algorithm (3-SAT), inclusion-exclusion (k-colorability).
Scribe: Xiaoyu He.
[PDF][TeX][video]
- Tuesday, Nov. 25 — zeta transform, Möbius inversion, streaming algorithms, necessity of randomization and approximation, distinct elements.
Scribe: Keno Fischer.
[PDF][TeX][video]
- Thursday, Nov. 27. NO CLASS (Happy Thanksgiving!).
- Tuesday, Dec. 2 — power of random signs: ℓ2 norm estimation, subspace embeddings (regression), Johnson-Lindenstrauss, deterministic point query.
Scribe: Nithin Tumma.
[PDF][TeX][video]