Algorithms in a Nutshell

Randomized Algorithms | 303

When All Else

Fails

Parallel Algorithms

A computational process may spawn several computational processes to work

simultaneously on subinstances of a problem. Using the same example from the

previous section, “Offline Algorithms,” it is possible to speed up the performance

ofn/2 SEQUENTIALSEARCHexecutions by executing these searches in parallel on

nprocessors. The resulting worst-case cost of the paralleln/2 searches is O(n). If

you are interested in pursuing this idea further, you should read the book by

Berman and Paul (2004) on the subject. You may also find it worthwhile to read

about actual systems that take advantage of parallelism afforded by multicore

processors; see Armstrong’sProgramming Erlang: Software for a Concurrent

World(2007).

Randomized Algorithms

An algorithm may use a stream of random bits (numbers) in solving a problem.

Often we may find fast algorithms to solve a problem when we assume access to a

stream of random bits. For practical purposes, one should be aware that streams

of random bits are very difficult to generate on deterministic computers. Though

we may generate streams of quasi-random bits that are virtually indistinguishable

from streams of truly random bits, the cost of generating these streams should not

be ignored.

Estimating the Size of a Set

As an example of the speedups that can be obtained in allowing probabilistic algo-

rithms, assume we want to estimate the size of a set ofnobjects, {x 1 ,...,xn}, with

distinct labels. That is, we want to estimate the valuen. It would be straightfor-

ward to count all the objects, at a cost of O(n). Clearly this process is guaranteed

to yield an exact answer. But if an incorrect estimate of the value ofnis tolerable,

assuming it could be computed more quickly, the algorithm described in

Example 10-1 is a faster alternative.

Example 10-1. Implementation of probabilistic counting algorithm

public static double computeK (int n) {

// Make sure we use data structure with efficient lookup.

Hashtable<Integer,Boolean> setS = new Hashtable<Integer,Boolean>( );

// Repeatedly probe to see if already located

int y = 1+((int)(Math.random( )*n));

while (!setS.containsKey(y)) {

setS.put(y, Boolean.TRUE);

y = 1+((int)(Math.random( )*n));

}

// return estimate of original size

int k = setS.size( );

return 2.0*k*k/Math.PI;

}

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