Review of discrete probability; Notion of randomized algorithms, motivating examples; Markov, Chebyshev inequalities, Chernoff bounds; Probabilistic method; Hashing, fingerprinting; Random walks and Markov chains. Program checkers; Polynomial identities; Randomized complexity classes, Probabilistically checkable proofs; some number theoretic problems; Approximate counting.
- Teacher: Surender Baswana