不可错过！哈佛大学《高级算法课程》课件与视频放出！CS 224: Advanced Algorithms

2022 年 1 月 23 日 专知

算法是一种定义明确的程序，用于执行一些计算任务。通常任务是给定的，而算法的工作是找到这样一个有效的过程，例如在处理时间和/或内存消耗方面。cs224是一门算法设计的高级课程，我们将涵盖的主题包括word RAM模型，数据结构，摊销，在线算法，线性规划，半定规划，近似算法，哈希，随机算法，快速指数时间算法，图算法，和计算几何。

http://people.seas.harvard.edu/~minilek/cs224/fall14/index.html

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²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: ℓ₂ norm estimation, subspace embeddings (regression), Johnson-Lindenstrauss, deterministic point query.
Scribe: Nithin Tumma. [PDF][TeX][video]