RANDOMIZED ALGORITHMS

Explore the purpose and reasons for randomized algorithms and the difference between a Las Vegas algorithm and Monte Carlo algorithm.

How do people predict the stock market? How can I sort through a large list of values fast? How do they predict what a nuclear reactor will do before building it? All these answers lie within randomness. Randomized (Stochastic) Algorithms play a large role in today’s data science. From sorting to artificial intelligence to business analytics, randomized algorithms play a huge role in our daily lives. Also known as probabilistic Turing machines, randomized algorithms use random numbers and probability to produce one of two outcomes: either the algorithm terminates with the right answer, or the algorithm terminates with an approximation of the right answer.

Probability- How likely an event is to occur, typically determined after many repeated trials.

Uniform Distribution- A probability distribution where every value has an equal probability.

Random number seed- A number used to initialize a random number generator to get a specified set of random numbers so the results are the same across runs.

Las Vegas Algorithm- a randomized algorithm that always gives the correct answer but in an indeterminate amount of time.

Monte Carlo Algorithm- a randomized algorithm that gives an answer with a specified amount of uncertainty within a determinate amount of time.

• If I were trying to predict the probability that it would rain today, would I want to use a Monte Carlo or Las Vegas Algorithm?

• If I were trying to find a person in a group of people, would I want to use a Monte Carlo or Las Vegas Algorithm?

• (CHALLENGE) If I were trying to sort a large list of values in smallest to largest with this pseudocode (randomized quicksort), would this be a Monte Carlo or Las Vegas Algorithm?

• What is the time complexity?

https://www.geeksforgeeks.org/randomized-algorithms/