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 
Decisionmaking under uncertainty 1: dynamic programming and linear programming 
Lecture notes 9  
Oct 7 
Decisionmaking 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 BenTal 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 ShalevShwartz.  
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: NPcompleteness and reductions 
Computational complexity: a modern approach by Arora and Barak. See chapter 2.  
Dec 5 
Final 