Course

Basic probability theory; randomized complexity classes; game-theoretic techniques; Markov, Chebyshev, and moment inequalities; limited independence; coupon collection and occupancy problems; tail inequalities and the Chernoff bound; conditional expectation; the probabilistic method; Markov chains and random walks; algebraic techniques; probability amplification and derandomization.

Lovasz Local Lemma and applications, the method of conditional probabilities. Randomized Data Structures: Hashing. Fingerprinting, Schwarzt-Zippel, Pattern Matching.Applications: Sorting and searching; data structures; combinatorial optimization and graph algorithms; geometric algorithms and linear programming; approximation and counting problems; parallel and distributed algorithms; online algorithms.

Text Books:

1. Motwani, and Randomized Algorithms. Cambridge, UK: Cambridge University Press, 1995.
2. Feller, William. An Introduction to Probability Theory and Its Applications.Vol. 1. New York, NY: John Wiley.
3. 3 .Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis., Cambridge University Press, 2nd edition.