Juraj Hromkovic Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms. Series: Texts in Theoretical Computer Science. An EATCS Series. Springer (2005). ISBN 3-540-23949-9. £30.50/€39.95/$49.95. 274 pp. Hardbound.
Mark Burgin · The Computer Journal · 2005
When the concept of the algorithm was formalized in mathematics and then adopted in computer science, one of the main assumptions was that an algorithm has to be deterministic. For instance, in such a fundamental book as [1], the following definition is given: Algorithm is a clerical (i.e., deterministic, bookkeeping) procedure which can be applied to any of a certain class of symbolic inputs and which will eventually yield, for each such input, a corresponding output. This understanding corresponded only deterministic theoretical models (Turing machines, λ-calculus, partial recursive functions etc.) to the notion of the algorithm. Moreover, those algorithms that were used in mathematics for millennia (for example, Euclid's algorithm) also supported the idea that an algorithm has to be deterministic. However, mathematicians and computer scientists found that the idea of algorithm is much broader than the deterministic restriction allows. As a result, randomness came into the algorithmic realm. In theory, it came, at first, in the guise of non-deterministic computational models (non-deterministic finite automata attributed to [2], pushdown automata [3, 4], non-deterministic Turing machines etc.) and then as probabilistic models (probabilistic Turing machines [5], probabilistic finite automata [6], etc.). In practice, probabilistic algorithms appeared even earlier than in theory. The first design and utilization of probabilistic algorithms under the name Monte Carlo methods is attributed to Ulam and Metropolis who in 1940s applied these methods to numerical problems in Los Alamos. However, this was at an empirical level, while the first theoretically grounded probabilistic algorithm was suggested by Solovay and Strassen [7] for finding whether a number is prime or not.