**Text:** Probability and Computing: Randomized Algorithms and
Probabilistic Analysis

by Michael Mitzenmacher and Eli Upfal

Cambridge University Press

A text I have used previously is available online at: Probability and Algorithms

Some other books:

Probability and Statistics with Reliability, Queueing,
and Computer Science Applications, 2nd Edition

by Kishor Trivedi

Wiley-Interscience, 2001

Randomized Algorithms

by Rajeev Motwani and Prabhakar Raghavan

Cambridge University Press, 1995

**Topics:** We will cover much of the material in Chapters 1-9.

**Possible additional topics:**

- Types of randomized algorithms: Monte Carlo, Las Vegas, Sherwood, RP, BPP
- Conditional probabilities, Markov chains, Hidden Markov Models
- Pseudorandom numbers
- Simulated annealing
- Genetic algorithms
- Primality testing and factoring
- Queuing theory
- An index page linking some further topics

**Topics actually covered:**

- Jan 18: Sections 1.1-2 Axioms, verifying polynomial equality
- Jan 23: Sections 1.3-4 Verifying matrix multiplication, min-cut
- Jan 23: Sections 2.1 -3 Expectation and Bernoulli and binomial random variables