Probability and Computing - Monsoon Semester (2014-15)
Time: Tu 14:00-17:00
Problem Sets and Exams
- PS1 [ pdf (out: 2 Sep, due: 16 Sep) ]
- PS2 [ pdf (out: 14 Oct, due: 28
- Aug 19: Introduction to discrete probability
Probability in Computing, Examples: Verifying Matrix
Multiplication, MINCUT, factorization of quadratic polynomials;
Discrete probability modeling, conditioning.
Ref: [ MU (Chap. 1), GS (Sec 1.1-1.4), Sud (Lec. 4,
last section; Lec. 5, section 1)]
- Aug 26:Application to primes and random variables
Independence; Primes: picking a random prime, testing primality;
birthday problem; random variables; expectation; linearity of expectation
Ref: [ MU (Chap 2) ]
- Sep 2: Applications of linearity of expectation
probability mass functions; conditional expectation; binomial and
geometric rvs; Applications: MAXCUT, Coupons collectors' problem,
randomized quicksort; Markov's inequality
Ref: [ MU (Chap 2) ]
- Sep 9: Tail bounds: Chebyshev and Chernoff
Variance, Chebyshev's Inequality, Chernoff bounds, sampling,
randomized load balancing
Ref: [ MU (Chap. 3-4) ]
- Sep 16: Poisson Distribution and Hashing
Balls and Bins, Poisson distribution, Hashing techniques
- Sep 23: Hashing and Random graphs
fingerprinting, Bloom filters, Random Graphs
(Erdos-Renyi Model, Bollobas degree sequence model, Barabasi-Albert
preferential alignment model)
- Oct 8: Markov Chains
Finite space, discrete time
Markov chains, stationary distributions, Irregularities:
periodicity, reducibility; regular Markov chains, Fundamental
theorem for finite state Markov chains, time-reversibility;
Applications: Pagerank and Metropolis algorithms.
- Oct 14: Markov Chains and continuous random variables
Proof of Fundamental theorem for finite state Markov chains;
Introduction to continuous random variables, uniform and exponential
distributions, probability density functions (pdfs), cumulative
density functions (cdfs), joint pdfs
Tentative list of topics
- Introduction, examples: verifying matrix multiplication, mincut
- Discrete probability, random variables, conditioning, independence
- Linearity of Expectation, Jensen's inequality, testing primes
- Birthday Problem, Binomial + Geometric rv's, MAXCUT
- Moments and Deviations: Markov's, Chebyshev's inequalities
- Chernoff Bounds, Application: load balancing
- Balls and bins, posson approximation
- Hashing, fingerprinting, bloom filters
- Probabilistic Method
- Markov Chains, Applications: Pagerank, Metropolis
- Continuous Random Variables
- Poisson Process
- Continuous Markov Chains
- Gaussian Random Variables, Central Limit Theorem
Students taking the course for credit will be expected to:
- Do problem sets (approx 1 pset every 2 weeks, 6 psets)
- Give the final exam
- Problems Sets - 75%
- Final Exam - 25%
G. Grimmett and D. Stirzaker.
Probability and Random Processes.
3rd Ed. Oxford University Press, 2001.
[ .html ]
M. Mitzenmacher and E. Upfal.
Probability and Computing.
Cambridge University Press, 2005.
6.966, Algebra and Complexity Theory, 1998.
A course offered at MIT (Fall 1998).
[ .html ]
This page has been accessed at least
times since 10 August, 2014.