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%