Algorithms in a Nutshell

Chapter 10. When All Else Fails

This chapter is different from the others chapters in this book. While the other chapters provide algorithms that solve common problems, here we present problems that can be solved by algorithms that are interesting in their own right. Knowledge of these algorithms should help designers determine how to apply them to solve seemingly very different problems.

Another difference is that randomness and probability were used in previous chapters when analyzing the average-case behavior of algorithms. Here the randomness is an essential part of the algorithms. Indeed, the probabilistic algorithms we describe here are interesting alternatives to deterministic algorithms. Running the same algorithm on the same input at two different times may provide very different answers. Sometimes we will tolerate wrong answers, and sometimes we will tolerate an algorithm's throwing up its (figurative) hands and saying it can't solve the problem.

One strong assumption is that the algorithms have access to a stream of random bits. It is hard to define randomness, though we have several tests that a sequence of random bits must satisfy. And it is hard to generate a sequence of bits that satisfy these tests.

Variations on a Theme

All the algorithms we considered in this book were expected to give exact answers to an instance of a problem on a sequential, deterministic computer. Much interesting research has been done by relaxing each of these four assumptions:

• Answers must be ...