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:
“I wish glib and indiscriminate critics of industrialists had some conception of the problems that have to be met by factory management.... General condemnation of employers is a favorite indoor sport of the uninformed intelligentsia who assume the role of lance- bearers for labor.”
—Mary Barnett Gilson (1877–?)
“Recent studies that have investigated maternal satisfaction have found this to be a better prediction of mother-child interaction than work status alone. More important for the overall quality of interaction with their children than simply whether the mother works or not, these studies suggest, is how satisfied the mother is with her role as worker or homemaker. Satisfied women are consistently more warm, involved, playful, stimulating and effective with their children than unsatisfied women.”
—Alison Clarke-Stewart (20th century)