CS5820 - Probability and Computing

#### Course Objectives:

To introduce the power of probability theory and randomization techniques in computer science, with particular emphasis on analyzing algorithms that employ randomization.

#### Course contents:

Introduction  Events, probability spaces, random variables, expectation, conditional expectation, tail bounds including Markovs inequality, Chebyshevs inequality, Chernoff bounds. Sample applications include Kargers min-cut algorithm, randomized quicksort, and permutation routing on the hypercube.
Common Probability Distributions  Bernoulli and binomial random variables, geometric distribution, coupon collectors problem, Poisson distribution, normal distribution, power law distributions.
Hashing with Applications  Balls into bins, chain hashing, Bloom filters, pairwise independence, Chebyshevs inequality for pairwise independent variables, universal hash functions, perfect hashing, the count-min sketch, the power of two choices, cuckoo hashing.
Probabilistic Method  The counting argument, the expectation argument, sample and modify, the second moment method, the conditional expectation inequality, the Lovasz local lemma.
Markov Chains and Random Walks  Basic definitions, stationary distribution, variation distance and mixing time and their relation to graph spectrum, random walks on undirected graphs, the Monte Carlo method, the Metropolis algorithm, coupling.
Martingales  Basic definitions, stopping time, Walds equation, Azuma-Hoeffding inequality.

#### Text Books:

Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by Mitzenmacher and Upfal, Cambridge University Press, 2005.

#### References

• Randomized Algorithms, by Motwani and Raghavan, Cambridge University Press, 1995.
• Concentration of Measure for the Analysis of Randomized Algorithms, by Dubhashi and Panconesi, Cambridge University Press, 2009.
• The Probabilistic method, by Alon and Spencer, 3rd edition, Wiley, 2008.

None

#### Parameters

 Credits Type Date of Introduction 3-1-0-0-8-12 Elective Jul 2015