Probability basics. Las Vegas and Monte Carlo Algorithms.
Moments and deviations: Occupancy problems, The Markov and Chebyshev Inequality, Randomized selection, two-point sampling, the stable marriage problem, the coupon collector problem.
Tail Inequalities: The Chernoff bound with applications in routing in a parallel computer, a wiring problem, set balancing problem. Martingales - stopping times, Wald's Equation, Azuma-Hoeffding Inequality, McDiarmid Inequality, Applications of tail inequalities for Martingales in a pattern matching problem, in a balls and bins problem, and in estimating the chromatic number of graphs, etc.
The probabilistic method: Overview of the basic method, applications in maximum satisfiability problem, expanding graphs, probability amplification, oblivious routing problem, etc. The Lovasz Local Lemma and its applications
Markov Chains and random walks: Definition and representation of Markov Chains, their application in designing randomized algorithms for 2-SAT and 3-SAT problems. Classification of states, stationary distributions, random walks on undirected graphs and their application in designing an algorithm for the s-t connectivity problem.