Randomized Algorithms
Las Vegas & Monte Carlo
An algorithm that uses random numbers to decide the next step is called a Randomized Algorithm.
For example, in Randomized Quick Sort[1], we use a random number to pick the next pivot (or we randomly shuffle the array). Typically, this randomness is used to reduce time complexity or space complexity in other standard algorithms.
Randomized algorithms are useful because it shows good average-case behavior and gives exact answers with high probability.
There are 2 types (with the name of 2 cities where people go for gambling:-D)
- Las Vegas Algorithms (LV)
Always give the correct answer. But slow (Comparatively) and need resources.
e.g: randomized quicksort, randomized selection
2. Monte Carlo Algorithms (MC)
Not always 100% correct. But fast.
e.g: Karger’s algorithm (Min cut)
We will first discuss Randomized Quicksort, which comes under LV algorithms.
Here Pivot element is selected randomly and partition is done accordingly.
QUICKSORT (A, p, r){if p < r
then q ← PARTITION(A, p, r)
QUICKSORT (A, p, q — 1)
QUICKSORT (A, q+1, r)}PARTITION (A, p, r){x ← A[p]
i ← p -1
Θ(n) where n = r-p+1
j ← r +1
while TRUE
repeat j ← j - 1
until A[ j ] ≤ x
repeat i ← i + 1
until A[ i ] ≥ x
if i < j
then exchange A[ i ] ↔A[ j ]
else return j
}
Refer the sample code written in Java. https://github.com/SkNuwanTissera/AdvancedAlgorithms/blob/master/Java_sources/RQuickSort.java
import java.util.*;
class RQuickSort
{
// This Function helps in calculating
// random numbers between low(inclusive)
// and high(inclusive)
static void random(int arr[],int low,int high)
{
Random rand= new Random();
int pivot = rand.nextInt(high-low)+low;
int temp1=arr[pivot];
arr[pivot]=arr[high];
arr[high]=temp1;
}
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
static int partition(int arr[], int low, int high)
{
// pivot is choosen randomly
random(arr,low,high);
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j = low; j < high; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] < pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
static void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver Code
public static void main(String args[])
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
sort(arr, 0, n-1);
System.out.println("Sorted array");
printArray(arr);
}
}When analyzing the complexity, worst case in O(n²) running time and average case O(n lg n)
Min Cut
Finding the line that cuts minimium edges. Graph can have multiple min cuts . One is shown above. Above graph have 2 mincuts.
A graph with n vertices can have at most n ∙ (n − 1)/2 distinct min cuts.
Exact algorithms are inefficient.
E.g., brute force approach, max-flow-min-cut
Karger’s (randomized) algorithm
This is an efficient O(n²) Monte Carlo algorithm. In this, Min cut can be found with high probability.
Based on the concept of Contraction of an edge (u,v)
– Merge the vertices u and v into one
• Reduces the total # of vertices of the graph by one
• All other edges connecting either u or v are “reattached” to the merged
node
– Iteratively contract randomly chosen edges until only two nodes
remain
– These 2 nodes represent a cut in the original graph
important: The algorithm may or may not find the min-cut. That is why its regarded as a Monte Carlo algorithm. The algorithm is not always accurate. But the running time of the algorithm is fairly in a good state.
References
