CS 224: Advanced Algorithms
CS 224: Advanced Algorithms (Fall 2014, Harvard Univ.). Instructor: Professor Jelani Nelson. An algorithm is a welldefined 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.
Lecture 01  Course Introduction, Word RAM and van Emde Boas Trees 
Lecture 02  Fusion Trees, WordLevel Parallelism 
Lecture 03  Hashing: Load Balancing, Kwise Independence, Dictionary 
Lecture 04  Hashing: Linear Probing (5wise 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, MovetoFront, Paging 
Lecture 09  Randomized Paging, Primal/Dual Online Algorithms 
Lecture 10  Online Primal/Dual: e/(e1) 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 14 
Lecture 15  Linear Programming: Standard Form, Vertices, Bases, Simplex 
Lecture 16  Simplex, Strong Duality, Complementary Slackness, Ellipsoid Algorithm 
Lecture 17  PathFollowing Interior Point, First Order Methods (Gradient Descent) 
Lecture 18  Second Order Methods (Newton's Method), PathFollowing Interior Point 
Lecture 19  Multiplicative Weights, Learning from Experts 
Lecture 20  Applying Multiplicative Weights to Linear Programmings 
Lecture 21  Faster st Max Flow: Scaling for Max Flow, Blocking Flows 
Lecture 22  LinkCut Trees 
Lecture 23  O(log2 n) Amortized Analysis of LinkCut Trees, Min Cost Max Flow 
Lecture 24  Fast ExponentialTime Algorithms: TSP, 3SAT, KColorability 
Lecture 25  Zeta Transform, Mobius Inversion, Streaming Algorithms 
Lecture 26  Streaming Algorithms, Power of Random Signs 
References 
CS 224: Advanced Algorithms
Instructor: Professor Jelani Nelson. Lecture Notes. Assignments. An algorithm is a welldefined procedure for carrying out some computational task.
