Advanced Algorithms by Jelani Nelson (Harvard University)

# click the upper-left icon to select videos from the playlist

source: Harvard University      2016年7月11日
Advanced Algorithms (COMPSCI 224)

Lecture 1 Logistics, course topics, word RAM, predecessor, van Emde Boas, y-fast tries. 1:28:19
Please see Problem 1 of Assignment 1 at http://people.seas.harvard.edu/~minil... for a corrected analysis of the space complexity of van Emde Boas trees
Lecture 2 Fusion trees, word-level parallelism, most significant set bit in constant time. 1:25:40
Lecture 3 Hashing: load balancing, k-wise independence, chaining, linear probing. 1:28:46
Lecture 4 Symmetrization, hashing: linear probing (5-wise indep.), bloom filters, cuckoo hashing, bloomier filters. 1:27:52
Lecture 5 Hashing: cuckoo hashing analysis, power of two choices. 1:21:37
Lecture 6 Amortized analysis, binomial heaps, Fibonacci heaps. 1:23:47
Lecture 7 Splay trees. 1:26:46
Lecture 8 Online algorithms, competitive analysis, move-to-front, paging. 1:24:06
Lecture 9 Randomized paging, packing/covering linear programs, weak duality, approximate complementary slackness, primal/dual online algorithms (2-competitive deterministic ski rental). 1:24:56
Lecture 10 Online primal/dual: e/(e-1) ski rental, set cover; approximation algorithms via dual fitting: set cover. 1:24:34
Lecture 11 Approximation algorithms via dual fitting (wrap-up), LP integrality gaps, definitions of PTAS/FPTAS/FPRAS, PTAS for knapsack. 1:25:41
Lecture 12 FPTAS (knapsack), FPRAS (DNF counting), semidefinite programming, Goemans-Williamson MAXCUT algorithm. 1:25:05
Lecture 13 Guest lecture: Rong Ge: Learning Topic Models. 1:21:46
Lecture 15 linear programming: standard form, vertices, bases, simplex. 1:26:14
Lecture 16 Simplex wrap-up, strong duality, complementary slackness, ellipsoid, intro to interior point. 1:24:58
Lecture 17 Path-following interior point, first order methods (gradient descent). 1:26:44
Lecture 18 second order methods (Newton's method), path-following interior point wrap-up. 1:24:43
Lecture 19 Learning from experts, multiplicative weights. 1:21:34
Lecture 20 Linear programming via multiplicative weights, flows, augmenting paths. 1:23:38
Lecture 21 Scaling for max flow, blocking flow. 1:27:09
Lecture 22 Preferred path decomposition, link-cut trees. 1:20:16
Lecture 23 Heavy-light decomposition, O(log2n) amortized analysis of link-cut trees, min cost max flow, min cost circulation, shortest augmenting paths. 1:26:46
Lecture 24 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). 1:26:03
Lecture 25 Zeta transform, Möbius inversion, streaming algorithms, necessity of randomization and approximation, distinct elements. 1:26:15
Lecture 26 Power of random signs: ℓ2 norm estimation, subspace embeddings (regression), Johnson-Lindenstrauss, deterministic point query. 1:25:03