Pseudo-random number generators are widely used in practical algorithms. Examples include simulation, number theory, fault tolerance, routing, cryptography, optimization, and perfect hashing.
Rabin popularised the idea of randomised algorithms, where randomness is incorporated into the algorithm instead of being assumed in the input data. Yao showed that there is a close connection between the complexity of probabilistic algorithms and the average-case complexity of deterministic algorithms. We give examples of the uses of randomness in computation, and discuss the contributions of Rabin, Yao and others.
If time permits (extremely unlikely), we shall consider the requirements for a good pseudo-random number generator, give examples of good and bad uniform generators, and describe a new class of generators for the normal distribution (based on a recent proposal by Wallace). These generators can give very fast vector/parallel implementations.
Compressed postscript file of the transparencies used in the lecture