CS5820 - Probability and Computing

Course Data :

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.

Pre-Requisites

    None

Parameters

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

Previous Instances of the Course


© 2016 - All Rights Reserved - Dept of CSE, IIT Madras
Website Credits