CS 224: Advanced Algorithms

Prof. Jelani Nelson     TFs: Zhixian Lei, Tom Morgan

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


Scribe Notes

  1. Tuesday, Jan. 24 — logistics, course topics, word RAM, predecessor, van Emde Boas, y-fast tries.
    Scribe: Jerry Ma. [PDF][TeX]

  2. Thursday, Jan. 26 — fusion trees.
    Scribe: Daniel Alabi. [PDF][TeX]

  3. Tuesday, Jan. 31 — Chernoff bound, hashing: load balancing, k-wise independence, dynamic dictionary, linear probing.
    Scribe: Saketh Rama. [PDF][TeX]

  4. Thursday, Feb. 2 — linear probing analysis (5-wise independence), moment bounds via symmetrization, approximate static membership (Bloom filters).
    Scribe: Rohil Prasad. [PDF][TeX]

  5. Tuesday, Feb. 7 — approximate static membership, cuckoo hashing, approximate static dictionary (Bloomier filters).
    Scribe: Rohit Agrawal. [PDF][TeX]

  6. Thursday, Feb. 9 — power of two choices, amortized analysis, binomial heaps.
    Scribe: Albert Chalom. [PDF][TeX]

  7. Tuesday, Feb. 14 — Fibonacci heaps, splay trees.
    Scribe: David Stoner. [PDF][TeX]

  8. Thursday, Feb. 16 — splay tree analysis, online algorithms, list update problem.
    Scribe: Tiffany Wu. [PDF][TeX]

  9. Tuesday, Feb. 21 — move-to-front analysis, paging.
    Scribe: Gavin McDowell. [PDF][TeX]

  10. Thursday, Feb. 23 — randomized paging, packing/covering LPs, online primal-dual.
    Scribe: Alex Wei. [PDF][TeX]

  11. Tuesday, Feb. 28 — online primal/dual: deterministic/randomized ski rental, set cover.
    Scribe: Meena Jagadeesan. [PDF][TeX]

  12. Thursday, Mar. 2 — approximation algorithms: weighted set cover, vertex cover, integrality gaps, PTAS/FPTAS/FPRAS.
    Scribe: Kevin Zhang. [PDF][TeX]

  13. Tuesday, Mar. 7 — PTAS (knapsack), FPTAS (knapsack), FPRAS (definite counting), semidefinite programming, MaxCut.
    Scribe: Hongyao Ma. [PDF][TeX]

  14. Thursday, Mar. 9 — semidefinite programming, max-cut, approximation algorithms in other settings: streaming algorithms, distinct elements.
    Scribe: Demi Guo. [PDF][TeX]

  15. Tuesday, Mar. 14. NO CLASS (Spring break).

  16. Thursday, Mar. 16. NO CLASS (Spring break).

  17. Tuesday, Mar. 21 — approximate nearest neighbor, locality sensitive hashing.
    Guest lecture: Piotr Indyk. [Slides]
    Scribe: Artidoro Pagnoni. [PDF][TeX][images (gzipped tar)]

  18. Thursday, Mar. 23 — power of random signs: AMS sketch, Thorup-Zhang, CountSketch, subspace embeddings.
    Scribe: Brian Hentschel. [PDF][TeX]

  19. Tuesday, Mar. 28 — linear programming: stanford form, vertices, bases, simplex.
    Scribe: Nicholas Hasselmo. [PDF][TeX]

  20. Thursday, Mar. 30 — strong duality, ellipsoid algorithm, interior point methods.
    Scribe: Dimitris Kalimeris. [PDF][TeX]

  21. Tuesday, Apr. 4 — first-order methods (gradient descent), second-order methods (Newton's method).
    Scribe: Matthew Deutsch. [PDF][TeX]

  22. Thursday, Apr. 6 — interior point analysis, learning from experts.
    Scribe: Noah Golowich. [PDF][TeX][BIB]

  23. Tuesday, Apr. 11 — multiplicative weights (with application to linear programming).
    Scribe: Thomas Orton. [PDF][TeX]

  24. Thursday, Apr. 13 — linear programming via MW wrap-up, max flow overview, Ford-Fulkerson.
    Scribe: Evan Yao. [PDF][TeX]

  25. Tuesday, Apr. 18 — blocking flows, Dinitz's algorithm.
    Scribe: Christina Chen. [PDF][TeX]

  26. Thursday, Apr. 20 — link-cut trees, heavy-light decomposition.
    Scribe: Stefan Gramatovici. [PDF][TeX]

  27. Tuesday, Apr. 25 — cell-probe model, chronogram technique, Ω(lg n / lglg n) lower bounds for dynamic partial sums and connectivity.
    Scribe: Jeff Cai. [PDF][TeX][images (gzipped tar)]