| Date | Topic | Reading | Additional readings/references (optional) |
|---|---|---|---|
| Sep 5 | Introduction, probability, hashing |
Lecture notes 1 | |
| Sep 10 | More hashing |
Lecture notes 2 | High Speed Hashing for Integers and Strings by Thorup. |
| Sep 12 |
Large deviation bounds and applications |
Lecture notes 3 | Concentration of Measure for the Analysis of Randomised Algorithms by Dubhashi and Panconesi. |
| Sep 17 |
Power of two choices |
Lecture notes 4 | Power of two choices survey by Mitzenmacher et al. |
| Sep 19 |
Hashing to real numbers and applications |
Lecture notes 5 | |
| Sep 24 |
Linear programming |
Lecture notes 6 | |
| Sep 26 |
Linear programming duality |
Lecture notes 7 | |
| Oct 1 |
Provable approximation via linear programming |
Lecture notes 8 | The design of approximation algorithms by Williamson and Shmoys. |
| Oct 3 |
Decision-making under uncertainty 1: dynamic programming and linear programming |
Lecture notes 9 | |
| Oct 8 |
Columbus day, no class |
||
| Oct 10 |
Decision-making under uncertainty 2: the multiplicative weight algorithm |
Lecture notes 10 | A survey on multiplicative weights by Arora, Hazan, and Kale. |
| Oct 15 |
Applications of the multiplicative weight algorithm |
||
| Oct 17 |
Applications of the multiplicative weight algorithm |
||
| Oct 22 |
High dimensional geometry, dimension reduction |
Lecture notes 12 | |
| Oct 24 |
Locality sensitive hashing and nearest neighbor search |
||
| Oct 29 |
Low rank approximation |
Lecture notes on SVD | |
| Oct 31 |
SVD using power method, spectral clustering |
Foundations of data science by Blum, Hopcroft, and Kannan. See chapter 3. | |
| Nov 5 |
Properties of convex functions, gradient descent |
Lecture notes on gradient descent | Lectures on modern convex optimization by Ben-Tal and Nemirovski. |
| Nov 7 |
Constrained gradient descent |
||
| Nov 12 |
Veterans' day, no class |
||
| Nov 14 |
Online and stochastic gradient descent |
Online learning and online convex optimization by Shalev-Shwartz. | |
| Nov 19 |
Game theory and equilibria |
Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani. | |
| Nov 21 |
Thanksgiving |
||
| Nov 26 |
Coding theory |
Essential coding theory by Guruswami, Rudra, and Sudan. | |
| Nov 28 |
Secret sharing and secured multiparty computation |
A graduate course in applied cryptography by Boneh and Shoup. The foundations of cryptography by Goldreich. |
|
| Dev 3 |
Intractability: NP-completeness and reductions |
Computational complexity: a modern approach by Arora and Barak. See chapter 2. | |
| Dec 5 |
Final |