CS 224: Advanced Algorithms
CS 224: Advanced Algorithms (Fall 2014, Harvard Univ.). Instructor: Professor Jelani Nelson. 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.
| 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 14 |
| 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 |
| References |
CS 224: Advanced Algorithms
Instructor: Professor Jelani Nelson. Lecture Notes. Assignments. An algorithm is a well-defined procedure for carrying out some computational task.
|