Lecture 1Logistics, Course Topics, Word RAM, Predecessor, van Emde Boas, y-fast Tries

Prev1 / 25Next

Lecture 1: Logistics, Course Topics, Word RAM, Predecessor, van Emde Boas, y-fast Tries

Logistics, Course Topics, Word RAM, Predecessor, van Emde Boas, y-fast Tries

Lecture 2: Fusion Trees, Word-Level Parallelism, Most Significant Set Bit

Lecture 3: Hashing, Load Balancing, k-wise Independence, Chaining, Linear Probing

Lecture 4: Symmetrization, Linear Probing, Bloom Filters, Cuckoo Hashing, Bloomier Filters

Lecture 5: Cuckoo Hashing Analysis and Power of Two Choices

Lecture 6: Amortized Analysis, Binomial Heaps, Fibonacci Heaps

Lecture 7: Splay Trees

Lecture 8: Online Algorithms, Competitive Analysis, Move-to-Front, Paging

Lecture 9: Randomized Paging, Packing and Covering Linear Programs, Online Primal-Dual Algorithms

Lecture 10: Online Primal-Dual, Ski Rental, Set Cover, Dual Fitting

Lecture 11: Dual Fitting, LP Integrality Gaps, PTAS, FPTAS, FPRAS, Knapsack

Lecture 12: FPTAS, FPRAS, Semidefinite Programming, Goemans-Williamson MAXCUT

Lecture 13: Topic Modeling and Nonnegative Matrix Factorization

Lecture 15: Linear Programming, Standard Form, Vertices, Bases, Simplex

Lecture 16: Simplex Wrap-Up, Strong Duality, Complementary Slackness, Ellipsoid, Interior Point

Lecture 17: Path-Following Interior Point and First Order Methods

Lecture 18: Second Order Methods and Path-Following Interior Point Wrap-Up

Lecture 19: Learning from Experts and Multiplicative Weights

Lecture 20: Linear Programming via Multiplicative Weights, Flows, Augmenting Paths

Lecture 21: Scaling for Max Flow and Blocking Flow

Lecture 22: Preferred Path Decomposition and Link-Cut Trees

Lecture 23: Heavy-Light Decomposition, Link-Cut Trees, Min Cost Max Flow

Lecture 24: Exponential-Time Algorithms, TSP, 3-SAT, Schoning's Algorithm, Inclusion-Exclusion

Lecture 25: Zeta Transform, Mobius Inversion, Streaming Algorithms, Distinct Elements

Lecture 26: Power of Random Signs, l2 Norm Estimation, Subspace Embeddings, Johnson-Lindenstrauss, Deterministic Point Query