Advanced Algorithms
In this course, we will cover topics such as Network Flows, Randomized Algorithms, Property Testing and Sublinear Algorithms. This course will give students an exposure to advanced deterministic algorithms and randomized algorithms, esp. space-efficient algorithms that are used to process massive data-sets which arise in machine learning and large-scale scientific computation, aka, Algorithms for Big Data. Students doing this course will gain a strong foundation in some of the techniques used in modern algorithms for big data.
| Unit | Sessions | Topics Covered |
|---|---|---|
|
Unit Probability Review + Tail Bounds |
Sessions 1 |
Topics Covered Expectation, Linearity of Expectation, Variance, Markov, Chebyshev, Chernoff |
|
Unit Network Flows |
Sessions 3 |
Topics Covered Ford-Fulkerson Algorithm, Max-Flow Min-Cut Theorem, Applications |
|
Unit Randomized Algorithms |
Sessions 3 |
Topics Covered Karger’s min-cut, Randomized median finding, 2-SAT, Primality testing |
|
Unit Property Testing + Sublinear Algorithms |
Sessions 2 |
Topics Covered Testing Sortedness, Estimating the number of connected components |
|
Unit The Probabilistic Method |
Sessions 1 | Topics Covered |