CS 224: Advanced Algorithms
Prof. Jelani
Nelson TFs: Zhixian Lei, Tom Morgan
[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-s17-staff@seas.harvard.edu. First-come first-served.
- Submit scribe notes (pdf + source) to
cs224-s17-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, Jan. 24 — logistics, course topics, word RAM, predecessor, van Emde Boas, y-fast tries.
Scribe: Jerry Ma.
[PDF][TeX]
- Thursday, Jan. 26 — fusion trees.
Scribe: Daniel Alabi.
[PDF][TeX]
- Tuesday, Jan. 31 — Chernoff bound, hashing: load balancing, k-wise independence, dynamic dictionary, linear probing.
Scribe: Saketh Rama.
[PDF][TeX]
- Thursday, Feb. 2 — linear probing analysis (5-wise independence), moment bounds via symmetrization, approximate static membership (Bloom filters).
Scribe: Rohil Prasad.
[PDF][TeX]
- Tuesday, Feb. 7 — approximate static membership, cuckoo hashing, approximate static dictionary (Bloomier filters).
Scribe: Rohit Agrawal.
[PDF][TeX]
- Thursday, Feb. 9 — power of two choices, amortized analysis, binomial heaps.
Scribe: Albert Chalom.
[PDF][TeX]
- Tuesday, Feb. 14 — Fibonacci heaps, splay trees.
Scribe: David Stoner.
[PDF][TeX]
- Thursday, Feb. 16 — splay tree analysis, online algorithms, list update problem.
Scribe: Tiffany Wu.
[PDF][TeX]
- Tuesday, Feb. 21 — move-to-front analysis, paging.
Scribe: Gavin McDowell.
[PDF][TeX]
- Thursday, Feb. 23 — randomized paging, packing/covering LPs, online primal-dual.
Scribe: Alex Wei.
[PDF][TeX]
- Tuesday, Feb. 28 — online primal/dual: deterministic/randomized ski rental, set cover.
Scribe: Meena Jagadeesan.
[PDF][TeX]
- Thursday, Mar. 2 — approximation algorithms: weighted set cover, vertex cover, integrality gaps, PTAS/FPTAS/FPRAS.
Scribe: Kevin Zhang.
[PDF][TeX]
- Tuesday, Mar. 7 — PTAS (knapsack), FPTAS (knapsack), FPRAS (definite counting), semidefinite programming, MaxCut.
Scribe: Hongyao Ma.
[PDF][TeX]
- Thursday, Mar. 9 — semidefinite programming, max-cut, approximation algorithms in other settings: streaming algorithms, distinct elements.
Scribe: Demi Guo.
[PDF][TeX]
- Tuesday, Mar. 14. NO CLASS (Spring break).
- Thursday, Mar. 16. NO CLASS (Spring break).
- Tuesday, Mar. 21 — approximate nearest neighbor, locality sensitive hashing.
Guest lecture: Piotr Indyk. [Slides]
Scribe: Artidoro Pagnoni.
[PDF][TeX][images (gzipped tar)]
- Thursday, Mar. 23 — power of random signs: AMS sketch, Thorup-Zhang, CountSketch, subspace embeddings.
Scribe: Brian Hentschel.
[PDF][TeX]
- Tuesday, Mar. 28 — linear programming: stanford form, vertices, bases, simplex.
Scribe: Nicholas Hasselmo.
[PDF][TeX]
- Thursday, Mar. 30 — strong duality, ellipsoid algorithm, interior point methods.
Scribe: Dimitris Kalimeris.
[PDF][TeX]
- Tuesday, Apr. 4 — first-order methods (gradient descent), second-order methods (Newton's method).
Scribe: Matthew Deutsch.
[PDF][TeX]
- Thursday, Apr. 6 — interior point analysis, learning from experts.
Scribe: Noah Golowich.
[PDF][TeX][BIB]
- Tuesday, Apr. 11 — multiplicative weights (with application to linear programming).
Scribe: Thomas Orton.
[PDF][TeX]
- Thursday, Apr. 13 — linear programming via MW wrap-up, max flow overview, Ford-Fulkerson.
Scribe: Evan Yao.
[PDF][TeX]
- Tuesday, Apr. 18 — blocking flows, Dinitz's algorithm.
Scribe: Christina Chen.
[PDF][TeX]
- Thursday, Apr. 20 — link-cut trees, heavy-light decomposition.
Scribe: Stefan Gramatovici.
[PDF][TeX]
- 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)]