Discrete Probability and Randomized Algorithms
Discrete Probability and Randomized
Algorithms (ECE5990)
For whom?
The course is intended for students who wish to add probabilistic
thinking to their toolbox. Knowledge of basic probability can be
helpful. Mathematical maturity is a prerequisite.
When, where?
Lectures: MW 840-955, 213 Phillips Hall
Office hours: Th 10-12, 382 Rhodes Hall
Instructor: Jayadev Acharya,
382 Rhodes Hall
News
Overview
The intersection of probability, and algorithm design has been
fruitful in many scientific domains, including but not limited to
communication protocols, networks, machine learning, optimization,
and quantum computation.
This course will introduce concepts in
discrete probability, and understand its applications in algorithm
design.
Tentative topics
- Basic Probability: Union bound, independence, Bayes rule
- Discrete random variables, linearity of expectations, Jensens inequality
- Bernoulli and Binomial random variables
- Polynomial identity testing, matrix multiplication
verification, randomized min-cut
- Geometric distributions, coupon collector's problem, randomized quicksort
- Concentration of measure: Chebyshev's inequality, Chernoff
bounds
- Anti concentration
- Randomized median finding
- Balls and bins: Poisson distribution, and Poisson sampling
- Hashing, Bloom filters, breaking symmetry
- Occupancy problems, packet routing, load balancing
- Randomized routing
- Random sampling, Monte carlo method, importance sampling
- Markov chains, coupling
- Entropy, compression
Books
- "Probability and Computing: Randomized Algorithms and Probabilistic Analysis", Michael Mitzenmacher, Eli Upfal
- "Randomized Algorithms", Rajeev Motwani, Prabhakar Raghavan
Grading
Assignments 60% (Worst set dropped)
Midterm 15%
Finals 25%