# click the upper-left icon to select videos from the playlist
source: Harvard University 2016年7月12日
Algorithms for Big Data (COMPSCI 229r)
Lecture 1 Logistics, course topics, basic tail bounds (Markov, Chebyshev, Chernoff, Bernstein), Morris' algorithm. 1:26:05
Lecture 2 Distinct elements, k-wise independence, geometric subsampling of streams. 1:23:57
Lecture 3 Necessity of randomized/approximate guarantees, linear sketching, AMS sketch, p-stable sketch for p less than 2 1:22:13
Lecture 4 P-stable sketch analysis, Nisan's PRG, ℓp estimation for p larger than 2 via max-stability. 1:21:03
Lecture 5 Analysis of ℓp estimation algorithm via max-stability, deterministic point query via incoherent matrices. 1:23:03
Lecture 6 CountMin sketch, point query, heavy hitters, sparse approximation. 1:25:47
Lecture 7 CountSketch, ℓ0 sampling, graph sketching. 1:19:26
Lecture 8 Amnesic dynamic programming (approximate distance to monotonicity). 1:22:02
Lecture 9 Communication complexity (indexing, gap hamming) + application to median and F0 lower bounds. 1:23:12
Lecture 10 Randomized and approximate F0 lower bounds, disjointness, Fp lower bound, dimensionality reduction (JL lemma). 1:18:47
Lecture 11 Khintchine, decoupling, Hanson-Wright, proof of distributional JL lemma. 1:19:20
Lecture 12 Alon's JL lower bound, beyond worst case analysis: suprema of gaussian processes, Gordon's theorem. 1:30:06
Lecture 13 ORS theorem (distributional JL implies Gordon's theorem), sparse JL. 1:22:13
Lecture 14 Sparse JL proof wrap-up, Fast JL Transform, approximate nearest neighbor. 1:21:38
Lecture 15 Approximate matrix multiplication with Frobenius error via sampling / JL, matrix median trick, subspace embeddings. 1:23:56
Lecture 16 Linear least squares via subspace embeddings, leverage score sampling, non-commutative Khintchine, oblivious subspace embeddings. 1:23:02
Lecture 17 Oblivious subspace embeddings, faster iterative regression, sketch-and-solve regression. 1:17:47
Lecture 18 Low-rank approximation, column-based matrix reconstruction, k-means, compressed sensing. 1:23:14
Lecture 19 RIP and connection to incoherence, basis pursuit, Krahmer-Ward theorem. 1:19:47
Lecture 20 Krahmer-Ward proof, Iterative Hard Thresholding. 1:19:58
Lecture 21 ℓ1/ℓ1 recovery, RIP1, unbalanced expanders, Sequential Sparse Matching Pursuit. 1:24:59
Lecture 22 Matrix completion. 1:25:06
Lecture 23 External memory model: linked list, matrix multiplication, B-tree, buffered repository tree, sorting. 1:22:52
Lecture 24 Competitive paging, cache-oblivious algorithms: matrix multiplication, self-organizing linked list, static B-tree, lazy funnelsort. 1:24:48
Lecture 25 MapReduce: TeraSort, minimum spanning tree, triangle counting. 1:21:17
1. Clicking ▼&► to (un)fold the tree menu may facilitate locating what you want to find. 2. Videos embedded here do not necessarily represent my viewpoints or preferences. 3. This is just one of my several websites. Please click the category-tags below these two lines to go to each independent website.
No comments:
Post a Comment