Randomized Algorithms and Pseudorandom Numbers

Randomized algorithms are analyzed as if unlimited amounts of perfect randomness were available, while pseudorandom number generation is usually studied from the perspective of cryptographic security or for the statistical properties of the numbers generated. Bach proposed studying the interaction between pseudorandom number generators and randomized algorithms. This paper follows Bach�s lead; the authors assume that a (small) random seed is available to start up a simple pseudorandom number generator that is then used for the randomized algorithm. Randomized algorithms are studied for (1) sorting, (2) selection. and (3) obhvious routing in networks. © 1993, ACM. All rights reserved.