Advanced Algorithms (Fall 2020)

General Information

Instructor:

Chihao Zhang

Time:

Monday
10:00am - 11:40am

Location:

DongShangYuan 107

Office Hour:

Monday
7:00 pm - 10:00 pm
Software Building 1402-2

Textbook

Probability and Computing, 2nd Edition, M. Mitzenmacher and E. Upfal

References

Randomized Algorithms, R. Motwani and P. Raghavan

The Probabilistic Method, 4th Edition, N. Alon and J. Spencer

Notes on Randomized Algorithms, J. Aspnes

Concentration Inequalities, S. Boucheron, G. Lugosi, P. Massart

Lecture Notes

[Nov 30][notes] Coupling, Sampling Proper Colorings
[Nov 23][notes] Introduction to Markov Chains
[Nov 16][notes] Algorithmic Lovász Local Lemma, Moser-Tardos Algorithm
[Nov 09][notes] Wald's Equation, Lovász Local Lemma
[Nov 02][notes] Stopping Time, Optional Stopping Theorem
[Oct 26][notes] Martingales, Doob Sequence, Azuma-Hoeffding, McDiarmid's Inequality
[Oct 19][notes] Multi-Armed Bandit, Explore-then-Commit, UCB
[Oct 12][notes] Johnson-Lindenstrauss Lemma, Bernstein's Inequality
[Oct 10][notes] Chernoff Bound, Hoeffding's Inequality
[Sep 28][notes] Poisson Approximation
[Sep 21][notes] Balls-into-Bins, Markov Inequality, Chebyshev Inequality
[Sep 14][notes] Linearity of Expectations, Quick Select, Karp-Upfal-Wigderson Inequality
[Sep 07][notes] Polynomial Identity Testing, Schwartz-Zippel Theorem, Karger's Min-Cut Algorithm, Karger-Stein