Randomized Algorithms: An algorithm that uses random numbers to decide what to do next anywhere in its logic is called a Randomized Algorithm.
For example, in Randomized Quick Sort, we use a random number to pick the next pivot (or we randomly shuffle the array)
Type of Randomized Algorithms
1. Las Vegas: A Las Vegas algorithm is an algorithm which uses randomness, but gives guarantees that the solution obtained for given problem is correct.
Advantage: Always produce a correct answer. Randomness affects the running time, not correctness. Expected running time is finite and analyzed probabilistically.
A randomized quick-sort algorithm where we randomly choose pivot is an example of Las-Vegas algorithm. The algorithm always sorts the array. The advantage we get with randomization is, there is no pattern for which the quick sort causes worst case (unlike choosing fixed pivot like a corner element causes worst case for sorted input)
Disadvantage: Time complexity of these algorithms is based on a random value and time complexity is evaluated as expected value.
Quick Short: This is a method to partition the array in place such that all elements to the left of the pivot element are smaller, while all elements to the right of the pivot are greater than the pivot. Then we recursively call the same procedure for left and right subarrays.
There are two types of algorithm for random pivoting. Lomuto Partitioning and Hoare Partitioning.
Algorithm for random pivoting using Lomuto Partitioning
partition(arr[], lo, hi)
pivot = arr[hi]
i = lo // place for swapping
for j := lo to hi – 1 do
if arr[j] <= pivot then
swap arr[i] with arr[j]
i = i + 1
swap arr[i] with arr[hi]
return i
partition_r(arr[], lo, hi)
r = Random Number from lo to hi
Swap arr[r] and arr[hi]
return partition(arr, lo, hi)
quicksort(arr[], lo, hi)
if lo < hi
p = partition_r(arr, lo, hi)
quicksort(arr, lo , p-1)
quicksort(arr, p+1, hi) ========================================================================================# Python implementation QuickSort using
# Lomuto's partition Scheme.
import random
'''
The function which implements QuickSort.
arr :- array to be sorted.
start :- starting index of the array.
stop :- ending index of the array.
'''
def quicksort(arr, start , stop):
if(start < stop):
# pivotindex is the index where the pivot lies in the array
pivotindex = partitionrand(arr,\
start, stop)
# At this stage the array is partially sorted around the pivot. # Separately sorting the left half of the array and the right # half of the array.
quicksort(arr , start , pivotindex-1)
quicksort(arr, pivotindex + 1, stop)
# This function generates random pivot swaps the first element with the pivot
# and calls the partition function.
def partitionrand(arr , start, stop):
# Generating a random number between the starting index of the array # and the ending index of the array.
randpivot = random.randrange(start, stop)
# Swapping the starting element of the array and the pivot
arr[start], arr[randpivot] = \
arr[randpivot], arr[start]
return partition(arr, start, stop)
'''
This function takes the first element as pivot,
places the pivot element at the correct position
in the sorted array. All the elements are re-arranged
according to the pivot, the elements smaller than the
pivot is places on the left and the elements
greater than the pivot is placed to the right of pivot.
'''
def partition(arr,start,stop):
pivot = start # pivot
# a variable to memorize where the
i = start + 1
# partition in the array starts from.
for j in range(start + 1, stop + 1):
# if the current element is smaller
# or equal to pivot, shift it to the
# left side of the partition.
if arr[j] <= arr[pivot]:
arr[i] , arr[j] = arr[j] , arr[i]
i = i + 1
arr[pivot] , arr[i - 1] =\
arr[i - 1] , arr[pivot]
pivot = i - 1
return (pivot)
# Driver Code
if __name__ == "__main__":
array = [11, 8, 9, 6, 2, 7]
quicksort(array, 0, len(array) - 1)
print(array) =======================================================================
Algorithm for random pivoting using using Hoare's partition Scheme.
partition(arr[], lo, hi)
pivot = arr[lo]
i = lo - 1 // Initialize left index
j = hi + 1 // Initialize right index
while(True)
// Find a value in left side greater than pivot
do
i = i + 1
while arr[i] < pivot
// Find a value in right side smaller than pivot
do
j = j - 1
while arr[j] > pivot
if i >= j then
return j
else
swap arr[i] with arr[j]
end while
partition_r(arr[], lo, hi)
r = Random number from lo to hi
Swap arr[r] and arr[lo]
return partition(arr, lo, hi)
quicksort(arr[], lo, hi)
if lo < hi
p = partition_r(arr, lo, hi)
quicksort(arr, lo, p)
quicksort(arr, p+1, hi) ======================================================================================== # Python implementation QuickSort using Hoare's partition Scheme.
import random
'''
The function which implements randomised
QuickSort, using Haore's partition scheme.
arr :- array to be sorted.
start :- starting index of the array.
stop :- ending index of the array.
'''
def quicksort(arr, start, stop):
if(start < stop):
# pivotindex is the index where
# the pivot lies in the array
pivotindex = partitionrand(arr,\
start, stop)
# At this stage the array is
# partially sorted around the pivot.
# separately sorting the left half of
# the array and the right
# half of the array.
quicksort(arr , start , pivotindex)
quicksort(arr, pivotindex + 1, stop)
# This function generates random pivot,
# swaps the first element with the pivot
# and calls the partition function.
def partitionrand(arr , start, stop):
# Generating a random number between
# the starting index of the array and
# the ending index of the array.
randpivot = random.randrange(start, stop)
# Swapping the starting element of
# the array and the pivot
arr[start], arr[randpivot] =\
arr[randpivot], arr[start]
return partition(arr, start, stop)
'''
This function takes the first element
as pivot, places the pivot element at
the correct position in the sorted array.
All the elements are re-arranged according
to the pivot, the elements smaller than
the pivot is places on the left and
the elements greater than the pivot is
placed to the right of pivot.
'''
def partition(arr,start,stop):
pivot = start # pivot
i = start - 1
j = stop + 1
while True:
while True:
i = i + 1
if arr[i] >= arr[pivot]:
break
while True:
j = j - 1
if arr[j] <= arr[pivot]:
break
if i >= j:
return j
arr[i] , arr[j] = arr[j] , arr[i]
# Driver Code
if __name__ == "__main__":
array = [
[11, 8, 9, 6, 2, 7]
quicksort(array, 0, len(array) - 1)
print(array)
================================================================
*************************************************************************
2. Monte Carlo Algorithms: A random algorithm is Monte-Carlo algorithms if it can give the wrong answer sometimes.
- Running time is typically fixed or bounded.
- Output may be incorrect with a small probability.
- Often used when approximate answers are acceptable or when error probability can be made tiny. These algorithms are used for solving physical simulation system and mathematical system.
The Monte-Carlo methods are used in places where deterministic algorithms take a lot time. Monte-Carlo integration is the most common application of Monte-Carlo algorithm. There are various methods used for integration by using Monte-Carlo methods such as,
i) Direct sampling methods which includes the stratified sampling, recursive stratified sampling, importance sampling.
ii) Random walk Monte-Carlo algorithm which is used to find out the integration for given problem.
iii) Gibbs sampling.
Applications of Randomized Algorithms
- Randomized algorithms have huge applications in Cryptography.
- Load Balancing.
- Number-Theoretic Applications: Primality Testing.
- Data Structures: Hashing, Sorting, Searching, Order Statistics and Computational Geometry.
- Algebraic identities: Polynomial and Matrix identity verification. Interactive proof systems.
- Mathematical programming: Faster algorithms for linear programming, Rounding linear program solutions to integer program solutions
- Graph algorithms: Minimum spanning trees, shortest paths, minimum cuts.
- Counting and Enumeration: Matrix permanent Counting combinatorial structures.
- Parallel and distributed computing: Deadlock avoidance distributed consensus.
- Probabilistic existence proofs: Show that a combinatorial object arises with non-zero probability among objects drawn from a suitable probability space.
- Derandomization: First devise a randomized algorithm then argue that it can be derandomized to yield a deterministic algorithm.
