Role of Randomness
In many cases, the space requirements for an algorithm can be drastically cut by using a randomized algorithm. For example, say we wish to know if two vertices in a graph of n vertices are in the same connected component of the graph. There is no known simple, deterministic, in-place algorithm to determine this, but if we simply start at one vertex and perform a random walk of about 20n3 steps, the chance that we will stumble across the other vertex provided that it's in the same component is very high. Similarly, there are simple randomized in-place algorithms for primality testing such as the Miller-Rabin primality test, and there are also simple in-place randomized factoring algorithms such as Pollard's rho algorithm. See RL and BPL for more discussion of this phenomenon.
Read more about this topic: In-place Algorithm
Famous quotes containing the words role of and/or role:
“The traditional American husband and father had the responsibilities—and the privileges—of playing the role of primary provider. Sharing that role is not easy. To yield exclusive access to the role is to surrender some of the potential for fulfilling the hero fantasy—a fantasy that appeals to us all. The loss is far from trivial.”
—Faye J. Crosby (20th century)
“Of course, some men are very effective caregivers [of elderly parents]. But this situation occurs far less frequently for males than females, because it is a role reversal. For women, caregiving is an expected duty; for men, it is an unexpected expression of love or devotion.”
—Tish Sommers (20th century)