Randomized Algorithms

How to assay Randomized Algorithms?

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

Classification

Las Vegas:

Advantages:

  • 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.

Advantages:

  • 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.

Disadvantages:

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

Flow chart:

Advantages:

  • 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

Disadvantages:

  • 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.

--

--

--

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

Recommended from Medium

Why You Should Learn Calculus

My thoughts on the Collatz Conjecture, using ma wimpy Primary School Brain

Linear Regression With Multiple Variables | Part 1

System of Linear Equations-REF, RREF & Rank.

Fall In Love With Science Subjects

Udacity Data Scientist Nanodegree : Prerequisite — Linear Algebra

Graph Representation Learning

Linear Algebra for Quantum Computing — Part 1

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
AKANKSHA POKALE

AKANKSHA POKALE

More from Medium

Data x Memoization

How does a total beginner start to learn Machine Learning?

Learn more about the Data Scientist position at Mytraffic thanks to David Tang

Data Engineering — W’s