Contents

1. Part 1. Origin and Tools
   • Buffon's Needle Experiment 1777
   • Pseudo Random Numbers
   • Random Number Generators

2. Part 2. Stochastic Methods
   • Computing Integrals
   • Local and Global Optimization
   • Discrete Event Simulation

3. Part 3. Probabilistic Algorithms for Discrete Problems
   • Paradigms for Prob Algorithms
     • Randomized Quicksort
     • Randomized Min-Cut Algorithm
   • Searching
     • Searching an Ordered List
     • Hashing
   • Finding and Using Large Primes
     • Primality Testing
     • Cryptography
   • Fingerprinting
     • Verifying Matrix Multiplication
     • Verifying Equality of Strings

Conclusions