Course No
M480
Credit
4
Approval
Syllabus
Inequalities of Markov and Chebyshev (median algorithm), first and second moment method (balanced allocation), inequalities of Chernoff (permutation routing) and Azuma (chromatic number), rapidly mixing Markov chains (random walk in hypercubes, card shuffling), probabilistic generating functions (random walk in d-dimensional lattice)
Reference Books
- R. Motwani, P. Raghavan, “Randomized Algorithms”, Cambridge University Press, 2004.
- M. Mitzenmacher, E. Upfal, “Probability and Computing: Randomized algorithms and probabilistic analysis”, Cambridge University Press, 2005