CS3341: Advanced Algorithms

Probability and Computing by Michael Mitzenmacher and Eli Upfal, Cambridge University Press
Notes on Randomized Algorithms by James Aspnes, notes for Yale CPSC 469/569
Advanced Algorithms by Anupam Gupta, notes for CMU 15-850

Week	Date	Topics	Lecture notes
1	02/18	Polynomial identity testing	Lecture 01
2	02/25	Karger's min-cut, Linearity of expectation	Lecture 02
3	03/04	Coupon collector, Karp-Upfal-Wigderson Bound
4	03/11	Balls-into-bins, Markov inequality, Monte Carlo vs. Las Vegas	Lecture 03
5	03/18	Chebyshev inequality, random graphs
6	03/25	Poisson approximation, Max load, Poisson process	Lecture 04
7	04/01	Generalized coupon collector, Chernoff bound	Lecture 05
8	04/08	Hoeffding inequality, Poisson tail bound
9	04/15	Martingale, Azuma-Hoeffding inequality	Lecture 06
	04/18	Optional stopping time, Wald's equation
10	04/22	Lovász local lemma	Lecture 07
	04/25	Moser-Tardos algorithm
11	04/29	Multiplicative Weights Update algorithm, convex functions	Lecture 08
12	05/06	Separating hyperplane, convex functions	Separating hyperplane Convex functions
	05/08	Convex optimization, gradient descent	Convex optimization Lecture 09
13	05/13	Lagrange multiplier method, KKT condition	Lecture 10
	05/15	Projected gradient descent, mirror descent	Lecture 11 Projected GD
14	05/20	MWU algorithm revisit, solving LP by MWU	Lecture 12
	05/22	Sampling problems, Markov chain basics	Lecture 13
15	05/27	Total variation distance, coupling lemma	Lecture 14
	05/29	Metropolis algorithm, mixing time, coupling method
16	06/03	Guest lecture by Chihao Zhang
	06/04	Final Quiz