Randomized algorithms use a degree of randomness as part of their logic. They are often simpler and faster than deterministic algorithms, especially in large-scale applications.

Example 1: Randomized Quick Sort

Concept

Randomized Quick Sort improves the performance of Quick Sort by randomly selecting the pivot element. This reduces the chances of encountering the worst-case time complexity.


public class RandomizedQuickSort {
  public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
      int pi = partition(arr, low, high);
      quickSort(arr, low, pi - 1);
      quickSort(arr, pi + 1, high);
    }
  }

  public static int partition(int[] arr, int low, int high) {
    int pivotIndex = low + (int)(Math.random() * (high - low + 1));
    int pivot = arr[pivotIndex];
    swap(arr, pivotIndex, high);
    int i = low - 1;
    for (int j = low; j < high; j++) {
      if (arr[j] <= pivot) {
        i++;
        swap(arr, i, j);
      }
    }
    swap(arr, i + 1, high);
    return i + 1;
  }

  public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

Explanation

The algorithm selects a random pivot and partitions the array around it, recursively sorting the subarrays. This approach ensures a better average-case time complexity.

Example 2: Monte Carlo Method

Concept

The Monte Carlo method uses randomness to solve problems that might be deterministic in principle. It is often used for numerical integration and simulations.


import java.util.Random;

public class MonteCarloPi {
  public static void main(String[] args) {
    int numPoints = 1000000;
    int insideCircle = 0;
    Random rand = new Random();
    
    for (int i = 0; i < numPoints; i++) {
      double x = rand.nextDouble();
      double y = rand.nextDouble();
      if (x * x + y * y <= 1) {
        insideCircle++;
      }
    }
    
    double piEstimate = 4.0 * insideCircle / numPoints;
    System.out.println("Estimated Pi: " + piEstimate);
  }
}

Explanation

This example estimates the value of Pi by randomly generating points in a unit square and calculating the ratio of points inside a quarter circle.

Example 3: Las Vegas Algorithm

Concept

Las Vegas algorithms always produce a correct result or notify failure. The randomness affects only the runtime, not the correctness.


import java.util.Arrays;
import java.util.Random;

public class LasVegasQuickSort {
  public static void main(String[] args) {
    int[] arr = {3, 6, 8, 10, 1, 2, 1};
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
  }

  public static void quickSort(int[] arr, int low, int high) {
    while (low < high) {
      int pi = partition(arr, low, high);
      if (pi - low < high - pi) {
        quickSort(arr, low, pi - 1);
        low = pi + 1;
      } else {
        quickSort(arr, pi + 1, high);
        high = pi - 1;
      }
    }
  }

  public static int partition(int[] arr, int low, int high) {
    int pivotIndex = low + new Random().nextInt(high - low + 1);
    int pivot = arr[pivotIndex];
    swap(arr, pivotIndex, high);
    int i = low - 1;
    for (int j = low; j < high; j++) {
      if (arr[j] <= pivot) {
        i++;
        swap(arr, i, j);
      }
    }
    swap(arr, i + 1, high);
    return i + 1;
  }

  public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

Explanation

This Las Vegas version of Quick Sort uses random pivot selection but guarantees correct sorting by retrying if necessary. The randomness affects only the efficiency.

Example 4: Randomized Min-Cut Algorithm

Concept

This algorithm finds a minimum cut in a graph by randomly contracting edges. It is a Monte Carlo algorithm, providing a correct result with high probability.


// Pseudo-code for Randomized Min-Cut
function RandomizedMinCut(Graph G) {
  while (G has more than 2 vertices) {
    choose an edge (u, v) uniformly at random
    merge u and v into a single vertex
    remove self-loops
  }
  return the cut represented by the remaining two vertices
}

Explanation

The algorithm repeatedly contracts random edges until only two vertices remain. The edges between these vertices represent a cut in the original graph.

Example 5: Random Sampling

Concept

Random sampling involves selecting a random subset of data from a larger dataset. It is used in various applications like estimating population statistics or simplifying complex datasets.


import java.util.Random;

public class RandomSampling {
  public static void main(String[] args) {
    int[] population = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int sampleSize = 3;
    int[] sample = randomSample(population, sampleSize);
    for (int value : sample) {
      System.out.print(value + " ");
    }
  }

  public static int[] randomSample(int[] population, int sampleSize) {
    Random rand = new Random();
    int[] sample = new int[sampleSize];
    for (int i = 0; i < sampleSize; i++) {
      int randomIndex = rand.nextInt(population.length);
      sample[i] = population[randomIndex];
    }
    return sample;
  }
}

Explanation

This example demonstrates how to randomly select a sample of elements from a larger array, which can be useful for data analysis and estimation tasks.