CS 224: Advanced Algorithms

Prof. Jelani Nelson     TF: Jeffrey Yan

[Home] [Lectures] [Assignments] [Project]


Scribe Notes

  1. Tuesday, Sept. 2 — logistics, course topics, word RAM, predecessor, van Emde Boas, y-fast tries.
    Scribe: Marcus Schorow. [PDF][TeX][video]

  2. Thursday, Sept. 4 — fusion trees, word-level parallelism, most significant set bit in constant time.
    Scribe: David Liu. [PDF][TeX][video]

  3. Tuesday, Sept. 9 — hashing: load balancing, k-wise independence, chaining, linear probing.
    Scribe: Thibaut Horel. [PDF][TeX][video]

  4. Thursday, Sept. 11 — symmetrization, hashing: linear probing (5-wise indep.), bloom filters, cuckoo hashing, bloomier filters.
    Scribe: Marco Gentili. [PDF][TeX][video]

  5. Tuesday, Sept. 16 — hashing: cuckoo hashing analysis, power of two choices.
    Scribe: Albert Wu. [PDF][TeX][video]

  6. Thursday, Sept. 18 — amortized analysis, binomial heaps, Fibonacci heaps.
    Scribe: Eric Balkanski. [PDF][TeX][FIG][video]

  7. Tuesday, Sept. 23 — splay trees.
    Scribe: Jarosław Błasiok. [PDF][TeX][BIB][video]

  8. Thursday, Sept. 25 — online algorithms, competitive analysis, move-to-front, paging.
    Scribe: Jean Pouget-Abadie. [PDF][TeX][video]

  9. 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]

  10. 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]

  11. 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]

  12. Thursday, Oct. 9 — FPTAS (knapsack), FPRAS (DNF counting), semidefinite programming, Goemans-Williamson MAXCUT algorithm.
    Scribe: Yifan Wu. [PDF][TeX][video]

  13. Tuesday, Oct. 14 — topic modeling, nonnegative matrix factorization.
    Guest lecture: Rong Ge.
    Scribe: Vasileios Nakos. [PDF][TeX][video]

  14. Thursday, Oct. 16 — approximate nearest neighbor, locality sensitive hashing.
    Guest lecture: Piotr Indyk.
    Scribe: Jao-ke Chin-Lee. [PDF][TeX][slides][no video]

  15. Tuesday, Oct. 21 — linear programming: standard form, vertices, bases, simplex.
    Scribe: Matt Rauen. [PDF][TeX][FIG][video]

  16. Thursday, Oct. 23 — simplex wrap-up, strong duality, complementary slackness, ellipsoid, intro to interior point.
    Scribe: Colin Lu. [PDF][TeX][video]

  17. Tuesday, Oct. 28 — path-following interior point, first order methods (gradient descent).
    Scribe: Ben Thompson. [PDF][TeX][video]

  18. Thursday, Oct. 30 — second order methods (Newton's method), path-following interior point wrap-up.
    Scribe: Xiaoyu He. [PDF][TeX][video]

  19. Tuesday, Nov. 4 — learning from experts, multiplicative weights.
    Scribe: Calvin Deng. [PDF][TeX][video]

  20. Thursday, Nov. 6 — linear programming via multiplicative weights, flows, augmenting paths.
    Scribe: David Palmer. [PDF][TeX][video]

  21. Tuesday, Nov. 11 — scaling for max flow, blocking flow.
    Scribe: Nithin Tumma. [PDF][TeX][video]

  22. Thursday, Nov. 13 — preferred path decomposition, link-cut trees.
    Scribe: Malcolm Granville. [PDF][TeX][video]

  23. 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]

  24. 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]

  25. Tuesday, Nov. 25 — zeta transform, Möbius inversion, streaming algorithms, necessity of randomization and approximation, distinct elements.
    Scribe: Keno Fischer. [PDF][TeX][video]

  26. Thursday, Nov. 27. NO CLASS (Happy Thanksgiving!).

  27. Tuesday, Dec. 2 — power of random signs: ℓ2 norm estimation, subspace embeddings (regression), Johnson-Lindenstrauss, deterministic point query.
    Scribe: Nithin Tumma. [PDF][TeX][video]