# How to assay Randomized Algorithms?

• Abundance of witnesses
• Fingerprint and hashing
• Random sampling
• Rapidly mixing Markov chains

# Las Vegas:

• Fast algorithm
• Always produces the correct result for the same input.
• Execution time depends on the output of the randomizer.

# Monte Carlo

## Characteristics:

• Users should aware of the input distribution.
• Output should generate random samples.
• While performing the experiment the outcome must be known.

• Makes use of the computer to give statistical sampling for numerical experiments.
• Implementation of this algorithm is easy.
• Solution provided to problems is approx.
• Used for both deterministic and stochastic problems.

• Result is not accurate as this method is only the approximation of true values.
• Consumes time.

## Flow chart:

• This algorithm is simple and easy to implement.
• Any deterministic algorithm can be converted into a randomized algorithm.
• Performance
• Efficient
• Compared to any of the deterministic algorithms they use little execution time and space.
• Show superior asymptotic bounds

• Not always reliable.
• Many of the algorithms may not terminate.
• The quality depends on the quality of the random number generator used.
• Unlike others, this algorithm does not use single design principle.

## Scope

• Number-theoretic algorithms Primality testing Monte Carlo_x0005_.
• Randomized algorithms can be used in Data structures, Sorting order statistics and searching computational geometry.
• Algebraic identities Polynomial and matrix identity verification Interactive proof systems.
• Randomized algorithms are best for Mathematical programming Faster algorithms.
• It can also be used in Graph algorithms, Minimum spanning trees, shortest paths finding algorithms, 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.

--

--

--

## More from AKANKSHA POKALE

Love podcasts or audiobooks? Learn on the go with our new app.

## Why You Should Learn Calculus ## Linear Regression With Multiple Variables | Part 1 ## System of Linear Equations-REF, RREF & Rank. ## Udacity Data Scientist Nanodegree : Prerequisite — Linear Algebra ## Graph Representation Learning ## Linear Algebra for Quantum Computing — Part 1  ## How does a total beginner start to learn Machine Learning?  