Courses with significant overlap with this course:

Semester of last offering:

Date of approval: dd-mmm-yyyy

Prerequisites:  

Course Contents

Review of discrete probability; Notion of randomized algorithms, motivating examples; Markov, Chebyshev inequalities, Chern off bounds; Probabilistic method; Hashing, fingerprinting; Random walks and Markov chains. Program checkers; Polynomial identities; Randomized complexity classes, Probabilistically check able proofs; some number theoretic problems; Approximate counting. 

Topics