13 Aug, 2019 Root User

Randomized Algorithm:

  • A probabilistic algorithm is an algorithm where the result and/or the way the result is obtained depend on chance. These algorithms are also sometimes called randomized algorithms.

  • It makes use of randomizer(random number generator) to make some decision in a algorithm.

  • The output and/or execution time of a randomized algorithm could also differ from run to run for the same input.

  • It can be categorized into:

    1. Las vegas algorithm

    2. Monte carlo algorithm

Las vegas Algorithm

  • this algorithm always same (correct) output for the same input.

  • Execution time of this algorithm is characterized as a random variable.

  • The execution time depends on the output of randomizer.

Monte Carlo Algorithm

<style type="text/css">
	@page { size: 8.5in 11in; margin: 0.79in }
	h3 { margin-top: 0.1in; margin-bottom: 0.08in; background: transparent; page-break-after: avoid }
	h3.western { font-family: "Comic Sans MS", cursive; font-size: 14pt; font-style: normal; font-weight: bold }
	h3.cjk { font-family: "Noto Sans CJK SC Regular"; font-size: 14pt; font-weight: bold }
	h3.ctl { font-family: "Lohit Devanagari"; font-size: 14pt; font-weight: bold }
	p { margin-bottom: 0.1in; line-height: 115%; background: transparent }
	a:visited { color: #800000; so-language: zxx; text-decoration: underline }
	a:link { color: #000080; so-language: zxx; text-decoration: underline }

  • Monte carlo is the algorithm whose output might differ from run to run for the same input.

  • It may generate the wrong answer sometimes that depends on the output of the randomizer.

  • The execution time is fixed.

Profile Image

Prosperous Nepal is possible only from technological innovation.

© 2021, All right reserved.