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

[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