Algorithms in a Nutshell

301

Chapter 10. When All Else Fails.................................................................................................................................................

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 prob-

lems 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 chap-

ters 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 algo-

rithm 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 algo-

rithm’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 inter-

esting research has been done by relaxing each of these four assumptions:

• Answers must be exact


• Only one instance is being solved


• The platform is sequential


• The platform is deterministic
  Relaxing these assumptions permits us to consider various other types of
  algorithms.

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use