Randomized
Algorithms
Randomization
• Randomized Algorithms special kind of algorithm,
making random choices during execution
• Such choices help in breaking symmetry in input
and applying different logic for repeated
executions
• For many applications, Randomized Algorithms
are easier to implement and more efficient than
Deterministic Algorithms
• May sometimes lead to incorrect results, but with a
very small probability
2
Deterministic Algorithm
Algorithm
Input Output
• Algorithms takes an input and produces an
output, based in specific logic
• Correctness of the algorithm can be verified
• Achieves identical output for the same input,
through every re-run
3
Randomized Algorithm
Algorithm
Input Output
Random Bits
• Algorithms takes additional input, random bits
• Output depends upon both input and random
bits
• Will not provide identical output for the same
input if run multiple times
4
Performance Impact
• Some inputs may cause ‘worst-case’ performance in
Deterministic algorithms
• Randomized algorithm changes execution path
using random bit input
• Any given input resulting in ‘worst-case’
performance highly unlikely
• Randomization improves execution time in most
cases
• Worst case performance is possible, but in very rare
occasions
5
Advantages & Disadvantages
• Advantages:
– Can be simpler to implement
– Running time better than Deterministic
– In some cases, Deterministic Algorithm may
not exist
• Disadvantages:
– Randomness is a resource
– Correctness is not always guaranteed
– Fast running time is also not always possible
6
Types of Algorithm
• Las Vegas Algorithms:
– Correctness is guaranteed
– Running time may vary
– Probability of worst case running time is low
• Monte Carlo Algorithms:
– Running time is fixed
– Output may not always be correct
– Probability of incorrect output is low
7
Quick Sort Algorithm
Quicksort(list, first, last)
Begin
If first < last then
Set p := Partition(list, first, last)
// p: pivot location, between first & last
Quicksort(list, first, p-1) // L-Part
Quicksort(list, p+1, last) // R-Part
End if
End
8
Quick Sort Analysis
• Position of pivot determines the running time of
the algorithm
• Pivot position chosen Deterministically as part
of design, hence does not change during
execution
• If the pivot is positioned at the smallest/largest
element of the list, execution time is impacted
• Worst case running time is O(n2)
9
Randomized Quick Sort
Quicksort(list, first, last)
Begin
If first < last then
Randomly choose pivot location, p, between first &
last
Partition(list, p, first, last)
Quicksort(list, first, p-1) // L-Part
Quicksort(list, p+1, last) // R-Part
End if
End
10
Randomized Quick Sort Analysis
• Position of pivot chosen randomly for every
run of quick sort
• Changes in pivot position reduces probability
of always choosing same position elements as
pivot
• Execution path is thus randomized
• Estimated complexity: O(n log n)
• Complexity can still be O(n2) in worst case, but
with very, very low probability
11
Polynomial Testing
• How to determine if two given polynomials
of x, F(x) & G(x) are equal?
• Deterministic Algorithm
– Convert two polynomials in standard format
– Check whether they are same
– Always correct
– Complexity: Θ(n2), where n is the degree of
polynomial
12
Polynomial Testing
• Probabilistic Algorithm
– Choose r, from a set of 100n possible values
– Evaluate F(r) and G(r)
– If F(r) = G(r), then F(x) is same as G(x)
– Complexity: Θ(n)
– Probability of incorrect output <= 1/100
– Error can be reduced through repeated
execution, e.g., use two numbers, r1 and r2,
check if F(r1) = G(r1) and F(r2) = G(r2)
13
Comparison
• Quick Sort:
– Las Vegas algorithm
– Always gives correct result
– Running time may vary
• Polynomial Testing:
– Monte Carlo algorithm
– Running time is fixed
– Result not always correct, though correctness
may be ‘boosted’ by repeated execution
14
Summary
• Randomization usually leads to quite simple
algorithms to design & implement
• Sometimes, Randomization Algorithms are de-
randomized to get deterministic algorithms
• Many complexity classes have been defined for
Randomized Algorithms, similar to P, NP for
deterministic algorithms
• In some cases, randomization make it easier to
solve problems
• Randomization is a resource (like space/time),
truly random inputs are very expensive to obtain
15
The End
