- Review of probability
- Types of probabilistic algorithms and problems
- One-sided and two-sided error
- Pseudo-random number generators
- RC4: a cryptographically strong random number generator
- Tests of randomness
- Inequalities for deviations from expectation
- The coupon collector problem
- Learning with a finite hypothesis space
- Chernoff bounds
- The birthday problem
- The Poisson distribution
- Hidden Markov Models
- Hidden Markov model example
- Skip lists
- Generating random permutations
- Simulated annealing
- Random Walks
- Markov chains
- Random walks on graphs
- Covering time for the line graph
- Queuing Theory
- The Pareto distribution
- Genetic algorithms and evolutionary computation
- Factoring and primality testing