| Date | Topic | Reading | Additional readings/references (optional) |
|---|---|---|---|
| Sep 5 | Introduction, probability, hashing |
Lecture notes 1 | |
| Sep 9 | Load balancing |
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 16 |
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 23 |
Linear programming |
Lecture notes on linear programming | |
| Sep 26 |
Linear programming duality |
||
| Sep 30 |
Provable approximation via linear programming |
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 7 |
Decision-making under uncertainty 2: the multiplicative weight algorithm |
Lecture notes on multiplicative weights | A survey on multiplicative weights by Arora, Hazan, and Kale. |
| Oct 10 |
Applications of the multiplicative weight algorithm |
||
| Oct 14 |
Columbus day, no class |
||
| Oct 17 |
Applications of the multiplicative weight algorithm |
||
| Oct 21 |
High dimensional geometry, dimension reduction |
Lecture notes on high dimensional geometry | |
| Oct 24 |
Locality sensitive hashing and nearest neighbor search |
||
| Oct 28 |
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 4 |
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 11 |
Veterans' day, no class |
||
| Nov 14 |
Online and stochastic gradient descent |
Online learning and online convex optimization by Shalev-Shwartz. | |
| Nov 18 |
Game theory and equilibria |
Lecture notes on equilibria | Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani. |
| Nov 21 |
Coding theory |
Lecture notes on coding theory and secured computation | Essential coding theory by Guruswami, Rudra, and Sudan. |
| Nov 25 |
Secret sharing and secured multiparty computation |
A graduate course in applied cryptography by Boneh and Shoup. The foundations of cryptography by Goldreich. |
|
| Nov 28 |
Thanksgiving |
||
| Dev 2 |
Intractability: NP-completeness and reductions |
Computational complexity: a modern approach by Arora and Barak. See chapter 2. | |
| Dec 5 |
Final |