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%