Loading…

Harvard

Advanced Algorithms

An algorithm is a well-defined procedure for carrying out some computational task. Typically the task is given, and the job of the algorithmist is to find such a procedure which is efficient, for example in terms of processing time and/or memory consumption. CS 224 is an advanced course in algorithm design, and topics we will cover include the word RAM model, data structures, amortization, online algorithms, linear programming, semidefinite programming, approximation algorithms, hashing, randomized algorithms, fast exponential time algorithms, graph algorithms, and computational geometry.

Instructor

Professor Jelani Nelson.

Computer science

2016

Lecture 01 - Course Introduction, Word RAM and van Emde Boas Trees

Lecture 02 - Fusion Trees, Word-Level Parallelism

Lecture 03 - Hashing: Load Balancing, K-wise Independence, Dictionary

Lecture 04 - Hashing: Linear Probing (5-wise Indep.), Bloom Filters, Cuckoo Hashing, Bloomier Filters

Lecture 05 - Hashing: Cuckoo Hashing Analysis, Power of Two Choices

Lecture 06 - Amortized Analysis, Binomial Heaps, Fibonacci Heaps

Lecture 07 - Splay Trees

Lecture 08 - Online Algorithms, Competitive Analysis, Move-to-Front, Paging

Lecture 09 - Randomized Paging, Primal/Dual Online Algorithms

Lecture 10 - Online Primal/Dual: e/(e-1) Ski Rental, Approximation Algorithms via Dual Fitting

Lecture 11 - Approximation Algorithms via Dual Fitting, LP Integrality Gaps, PTAS/FPTAS/FPRAS

Lecture 12 - FPTAS (Knapsack), FPRAS (DNF Counting), Semidefinite Programming

Lecture 13 - Learning Topic Models; Machine Learning Problems

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

Lecture 16 - Simplex, Strong Duality, Complementary Slackness, Ellipsoid Algorithm

Lecture 17 - Path-Following Interior Point, First Order Methods (Gradient Descent)

Lecture 18 - Second Order Methods (Newton's Method), Path-Following Interior Point

Lecture 19 - Multiplicative Weights, Learning from Experts

Lecture 20 - Applying Multiplicative Weights to Linear Programmings

Lecture 21 - Faster s-t Max Flow: Scaling for Max Flow, Blocking Flows

Lecture 22 - Link-Cut Trees

Lecture 23 - O(log2 n) Amortized Analysis of Link-Cut Trees, Min Cost Max Flow

Lecture 24 - Fast Exponential-Time Algorithms: TSP, 3-SAT, K-Colorability

Lecture 25 - Zeta Transform, Mobius Inversion, Streaming Algorithms

Lecture 26 - Streaming Algorithms, Power of Random Signs