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

- 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
. First-come first-served.`cs224-f14-staff@seas.harvard.edu` - 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.)

- 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(log
^{2}n) 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]