Applications and Scope

The Monte-carlo methods has wider range of applications. It uses in various areas like physical science, Design and visuals, Finance and business, Telecommunication etc. In general Monte carlo methods are used in mathematics. By generating random numbers we can solve the various problem. The problems which are complex in nature or difficult to solve are solved by using Monte-carlo algorithms. Monte carlo integration is the most common application of Monte-carlo algorithm.

The deterministic algorithm provides a correct solution but it takes long time or its runtime is large. This run-time can be improved by using the Monte carlo integration algorithms. 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.

Consider a tool that basically does sorting. Let the tool be used by many users and there are few users who always use tool for already sorted array. If the tool uses simple (not randomized) QuickSort, then those few users are always going to face worst case situation. On the other hand if the tool uses Randomized QuickSort, then there is no user that always gets worst case. Everybody gets expected O(n Log n) time.
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.

Randomized algorithms are algorithms that use randomness as a key component in their operation. They can be used to solve a wide variety of problems, including optimization, search, and decision-making. Some examples of applications of randomized algorithms include:

Monte Carlo methods: These are a class of randomized algorithms that use random sampling to solve problems that may be deterministic in principle, but are too complex to solve exactly. Examples include estimating pi, simulating physical systems, and solving optimization problems.
Randomized search algorithms: These are algorithms that use randomness to search for solutions to problems. Examples include genetic algorithms and simulated annealing.
Randomized data structures: These are data structures that use randomness to improve their performance. Examples include skip lists and hash tables.
Randomized load balancing: These are algorithms used to distribute load across a network of computers, using randomness to avoid overloading any one computer.
Randomized encryption: These are algorithms used to encrypt and decrypt data, using randomness to make it difficult for an attacker to decrypt the data without the correct key.

Example 1:

C++

#include <iostream>
#include <algorithm>
#include <random>
 
// Generates a random permutation of the given array
void random_permutation(int* array, int size) {
  // Create a random number generator
  std::mt19937 rng(std::random_device{}());
 
  // Shuffle the array using the random number generator
  std::shuffle(array, array + size, rng);
}
 
int main() {
  int array[] = {1, 2, 3, 4, 5};
  int size = 5;
 
  // Generate a random permutation of the array
  random_permutation(array, size);
 
  // Print the shuffled array
  for (int i = 0; i < size; i++) {
    std::cout << array[i] << " ";
  }
  std::cout << std::endl;
 
  return 0;
}

Java

import java.util.Random;
 
public class GFG {
  // Generates a random permutation of the given array
  public static void randomPermutation(int[] array) {
    Random rng = new Random();
    for (int i = array.length - 1; i > 0; i--) {
      int j = rng.nextInt(i + 1);
      // swap the values at indices i and j
      int temp = array[i];
      array[i] = array[j];
      array[j] = temp;
    }
  }
 
  public static void main(String[] args) {
    int[] array = {1, 2, 3, 4, 5};
    randomPermutation(array);
    // Print the shuffled array
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println();
  }
}

Python

import random
 
# Generates a random permutation of the given array
 
def random_permutation(array):
    # Shuffle the array using the random number generator
    random.shuffle(array)
 
array = [1, 2, 3, 4, 5]
 
# Generate a random permutation of the array
random_permutation(array)
 
# Print the shuffled array
print(array)

C#

using System;
using System.Linq;
 
class Program {
    static void Main(string[] args)
    {
        int[] array = { 1, 2, 3, 4, 5 };
        Random rng = new Random();
 
        // Generate a random permutation of the array
        array = array.OrderBy(x = > rng.Next()).ToArray();
 
        // Print the shuffled array
        Console.WriteLine(string.Join(" ", array));
    }
}

Javascript

function random_permutation(array) {
  // Shuffle the array using the random number generator
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
}
 
let array = [1, 2, 3, 4, 5];
 
// Generate a random permutation of the array
random_permutation(array);
 
// Print the shuffled array
console.log(array.join(" "));

Output

5 1 4 2 3

Example 2 :

C++

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>
 
// Find the median of a list of numbers
int find_median(std::vector<int> numbers)
{
    int n = numbers.size();
    if (n == 0) {
        return -1;
    }
    if (n == 1) {
        return numbers[0];
    }
 
    // Shuffle the list to ensure a random ordering
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(numbers.begin(), numbers.end(), g);
 
    // Find the median by selecting the middle element
    return numbers[n / 2];
}
 
int main()
{
    std::vector<int> numbers1 = { 1, 2, 3, 4, 5 };
    std::vector<int> numbers2 = { 1, 2, 3, 4, 5, 6 };
    std::vector<int> numbers3 = {};
    std::vector<int> numbers4 = { 7 };
 
    // Example usage
    std::cout << find_median(numbers1)
              << std::endl; // Output: 3
    std::cout
        << find_median(numbers2)
        << std::endl; // Output: 3 or 4 (randomly chosen)
    std::cout << find_median(numbers3)
              << std::endl; // Output: -1
    std::cout << find_median(numbers4)
              << std::endl; // Output: 7
 
    return 0;
}

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
 
public class Main {
    public static void main(String[] args)
    {
        ArrayList<Integer> numbers1
            = new ArrayList<Integer>();
        Collections.addAll(numbers1, 1, 2, 3, 4, 5);
        ArrayList<Integer> numbers2
            = new ArrayList<Integer>();
        Collections.addAll(numbers2, 1, 2, 3, 4, 5, 6);
        ArrayList<Integer> numbers3
            = new ArrayList<Integer>();
        ArrayList<Integer> numbers4
            = new ArrayList<Integer>();
        Collections.addAll(numbers4, 7);
 
        // Example usage
        System.out.println(
            find_median(numbers1)); // Output: 3
        System.out.println(find_median(
            numbers2)); // Output: 3 or 4 (randomly chosen)
        System.out.println(
            find_median(numbers3)); // Output: null
        System.out.println(
            find_median(numbers4)); // Output: 7
    }
 
    // Find the median of a list of numbers
    public static Integer
    find_median(ArrayList<Integer> numbers)
    {
        int n = numbers.size();
        if (n == 0) {
            return null;
        }
        if (n == 1) {
            return numbers.get(0);
        }
 
        // Shuffle the list to ensure a random ordering
        Collections.shuffle(numbers, new Random());
 
        // Find the median by selecting the middle element
        return numbers.get(n / 2);
    }
}

Python3

from random import shuffle
 
def find_median(numbers):
    n = len(numbers)
    if n == 0:
        return None
    if n == 1:
        return numbers[0]
 
    # Shuffle the list to ensure a random ordering
    shuffle(numbers)
 
    # Find the median by selecting the middle element
    return numbers[n // 2]
 
# Example usage
print(find_median([1, 2, 3, 4, 5]))  # Output: 3
print(find_median([1, 2, 3, 4, 5, 6]))  # Output: 3 or 4 (randomly chosen)
print(find_median([]))  # Output: None
print(find_median([7]))  # Output: 7

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
class MainClass {
public static void Main (string[] args) {
       List<int> numbers1 = new List<int>() {1, 2, 3, 4, 5};
       List<int> numbers2 = new List<int>() {1, 2, 3, 4, 5, 6};
       List<int> numbers3 = new List<int>();
       List<int> numbers4 = new List<int>() {7};
// Example usage
        Console.WriteLine(find_median(numbers1)); // Output: 3
        Console.WriteLine(find_median(numbers2)); // Output: 3 or 4 (randomly chosen)
        if(find_median(numbers3)==null)      
        Console.WriteLine("Null"); // Output: null
        Console.WriteLine(find_median(numbers4)); // Output: 7
 
}
 
// Find the median of a list of numbers
public static int? find_median(List<int> numbers) {
      int n = numbers.Count();
      if (n == 0) {
       return null;
       }
       if (n == 1) {
      return numbers[0];
}
 
// Shuffle the list to ensure a random ordering
Random rng = new Random();
numbers = numbers.OrderBy(a => rng.Next()).ToList();
 
// Find the median by selecting the middle element
return numbers[n / 2];
}}

Javascript

function find_median(numbers) {
  let n = numbers.length;
  if (n == 0) {
    return null;
  }
  if (n == 1) {
    return numbers[0];
  }
 
  // Shuffle the list to ensure a random ordering
  for (let i = n - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [numbers[i], numbers[j]] = [numbers[j], numbers[i]];
  }
 
  // Find the median by selecting the middle element
  return numbers[(Math.floor(n / 2))];
}
 
// Example usage
console.log(find_median([1, 2, 3, 4, 5])); // Output: 3
console.log(find_median([1, 2, 3, 4, 5, 6])); // Output: 3 or 4 (randomly chosen)
console.log(find_median([])); // Output: null
console.log(find_median([7])); // Output: 7

Output

4
6
None
7

Sources: http://theory.stanford.edu/people/pragh/amstalk.pdf https://en.wikipedia.org/wiki/Randomized_algorithm

C++

Java

Python

C#

Javascript

C++

Java

Python3

C#

Javascript

Randomized Algorithms | Set 2 (Classification and Applications)

Contact Us

Applications and Scope

C++

Java

Python

C#

Javascript

C++

Java

Python3

C#

Javascript

Randomized Algorithms | Set 2 (Classification and Applications)

Similar Reads

Contact Us