Randomized Algorithms | Set 2 (Classification and Applications)
We strongly recommend to refer below post as a prerequisite of this. Randomized Algorithms | Set 1 (Introduction and Analysis)
Classification
Randomized algorithms are classified in two categories.
Las Vegas:
A Las Vegas algorithm were introduced by Laszlo Babai in 1979.
A Las Vegas algorithm is an algorithm which uses randomness, but gives guarantees that the solution obtained for given problem is correct. It takes the risk with resources used. A quick-sort algorithm is a simple example of Las-Vegas algorithm. To sort the given array of n numbers quickly we use the quick sort algorithm. For that we find out central element which is also called as pivot element and each element is compared with this pivot element. Sorting is done in less time or it requires more time is dependent on how we select the pivot element. To pick the pivot element randomly we can use Las-Vegas algorithm.
Definition:
A randomized algorithm that always produce correct result with only variation from one aun to another being its running time is known as Las-Vegas algorithm.
OR
A randomized algorithm which always produces a correct result or it informs about the failure is known as Las-Vegas algorithm.
OR
A Las-Vegas algorithm take the risk with the resources used for computation but it does not take risk with the result i.e. it gives correct and expected output for the given problem.
Let us consider the above example of quick sort algorithm. In this algorithm we choose the pivot element randomly. But the result of this problem is always a sorted array. A Las-Vegas algorithm is having one restriction i.e. the solution for the given problem can be found out in finite time. In this algorithm the numbers of possible solutions arc limited. The actual solution is complex in nature or complicated to calculate but it is easy to verify the correctness of candidate solution.
These algorithms always produce correct or optimum result. Time complexity of these algorithms is based on a random value and time complexity is evaluated as expected value. For example, Randomized Quick Sort always sorts an input array and expected worst case time complexity of Quick Sort is O(nLogn).
Relation with the Monte-Carlo Algorithms:
- The Las-Vegas algorithm can be differentiated with the Monte-carlo algorithms in which the resources used to find out the solution are bounded but it does not give guarantee that the solution obtained is accurate.
- In some applications by making early termination a Las-Vegas algorithm can be converted into Monte-Carlo algorithm.
Complexity Analysis:
The complexity class of given problem which is solved by using a Las-Vegas algorithms is expect that the given problem is solved with zero error probability and in polynomial time.
This zero error probability polynomial time is also called as ZPP which is obtained as follows,
ZPP = RP ? CO-RP
Where, RP = Randomized polynomial time.
Randomized polynomial time algorithm always provide correct output when the correct output is no, but with a certain probability bounded away from one when the answer is yes. These kinds of decision problem can be included in class RP i.e. randomized where polynomial time.
That is how we can solve given problem in expected polynomial time by using Las-Vegas algorithm. Generally there is no upper bound for Las-vegas algorithm related to worst case run time.
Monte Carlo:
The computational algorithms which rely on repeated random sampling to compute their results such algorithm are called as Monte-Carlo algorithms.
OR
The random algorithm is Monte-carlo algorithms if it can give the wrong answer sometimes.
Whenever the existing deterministic algorithm is fail or it is impossible to compute the solution for given problem then Monte-Carlo algorithms or methods are used. Monte-carlo methods are best repeated computation of the random numbers, and that’s why these algorithms are used for solving physical simulation system and mathematical system.
This Monte-carlo algorithms are specially useful for disordered materials, fluids, cellular structures. In case of mathematics these method are used to calculate the definite integrals, these integrals are provided with the complicated boundary conditions for multidimensional integrals. This method is successive one with consideration of risk analysis when compared to other methods.
There is no single Monte carlo methods other than the term describes a large and widely used class approaches and these approach use the following pattern.
1. Possible inputs of domain is defined.
2. By using a certain specified probability distribution generate the inputs randomly from the domain.
3. By using these inputs perform a deterministic computation.
4.The final result can be computed by aggregating the results of the individual computation.
Produce correct or optimum result with some probability. These algorithms have deterministic running time and it is generally easier to find out worst case time complexity. For example this implementation of Karger’s Algorithm produces minimum cut with probability greater than or equal to 1/n2 (n is number of vertices) and has worst case time complexity as O(E). Another example is Fermat Method for Primality Testing. Example to Understand Classification:
Consider a binary array where exactly half elements are 0 and half are 1. The task is to find index of any 1.
A Las Vegas algorithm for this task is to keep picking a random element until we find a 1. A Monte Carlo algorithm for the same is to keep picking a random element until we either find 1 or we have tried maximum allowed times say k. The Las Vegas algorithm always finds an index of 1, but time complexity is determined as expect value. The expected number of trials before success is 2, therefore expected time complexity is O(1). The Monte Carlo Algorithm finds a 1 with probability [1 – (1/2)k]. Time complexity of Monte Carlo is O(k) which is deterministic
Optimization of Monte-Carlo Algorithms:
- In general the Monte-carlo optimization techniques are dependent on the random walks. The program for Monte carlo algorithms move in multidimensional space around the generated marker or handle. It wanted to move to the lower function but sometimes moves against the gradient.
- In numerical optimization the numerical simulation is used which effective and efficient and popular application for the random numbers. The travelling salesman problem is an optimization problem which is one of the best examples of optimizations.
- There are various optimization techniques available for Monte-carlo algorithms such as Evolution strategy, Genetic algorithms, parallel tempering etc.
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( " " )); |
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 |
4 6 None 7
Sources: http://theory.stanford.edu/people/pragh/amstalk.pdf https://en.wikipedia.org/wiki/Randomized_algorithm
Contact Us