Algorithms in a Nutshell

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 algorithms, assume we want to estimate the size of a set of n objects, {x₁, ..., x_n}, with distinct labels. That is, we want to estimate the value n. It would be straightforward 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 of n is 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 ...