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:
“Where we come from in America no longer signifies—it’s where we go, and what we do when we get there, that tells us who we are.
The irony of the role of women in my business, and in so many other places, too, was that while we began by demanding that we be allowed to mimic the ways of men, we wound up knowing we would have to change those ways. Not only because those ways were not like ours, but because they simply did not work.”
—Anna Quindlen (b. 1952)
“If women’s role in life is limited solely to housewife/mother, it clearly ends when she can no longer bear more children and the children she has borne leave home.”
—Betty Friedan (20th century)