Explain Randomized Algorithms.

32views

written 8.4 years ago by

teamques10 ★ 68k

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.
The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits.
The analysis of the average-case performance of quicksort depends on the input being randomly ordered. This assumption is not likely to be strictly valid in many practical situations. In general, this situation reflects one of the most serious challenges in the analysis of algorithms: the need to properly formulate models of inputs that might appear in practice.
Fortunately, there is often a way to circumvent this difficulty: “randomize” the inputs before using the algorithm. For sorting algorithms, this simply amounts to randomly permuting the input file before the sort.
If this is done, then probabilistic statements about performance such as those made earlier are completely valid and will accurately predict performance in practice, no matter what the input.
Often, it is possible to achieve the same result with less work, by making a random choice whenever the algorithm could take one of several actions.
For quicksort, this principle amounts to choosing the element to be used as the partitioning element at random, rather than using the element at the end of the array each time. If this is implemented with care then, again, it validates the probabilistic analysis given earlier.
The example of the analysis of quicksort that we have been considering perhaps illustrates an idealized methodology: not all algorithms can be as smoothly dealt with as this. A full analysis like this one requires a fair amount of effort that should be reserved only for our most important algorithms.
Fortunately, as we will see, there are many fundamental methods that do share the basic ingredients that make analysis worthwhile, where we can
Specify realistic input models.
Derive mathematical models that describe costs.
Develop concise, accurate solutions.
Use the solutions to compare variants and compare with other algorithms, and help adjust values of algorithm parameters.
Most often, we skip the parts of the methodology outlined above that are program-speciŀc to concentrate either on algorithm design, where rough estimates of the running time may suffice, or on the mathematical analysis, where the formulation and solution of the mathematical problem involved are of most interest.
These are the areas involving the most significant intellectual challenge, and deserve the attention that they get.
We study permutations, trees, strings, tries, words, and mappings because they are all both widely studied combinatorial structures and widely used data structures and because “random” structures are both straightforward and realistic.
This material is important in many applications beyond the analysis of algorithms
In some cases, algorithms that seem to be quite simple can lead to quite intricate mathematical analyses in other cases, algorithms that are apparently rather complicated can be dealt with in a straightforward manner.
In both situations, analyses can uncover significant differences between algorithms that have direct bearing on the way they are used in practice.
One advantage of this approach is that the programs are complete and unambiguous descriptions of the algorithms.
Another is that readers may run empirical tests to validate mathematical results.

ADD COMMENT EDIT