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