Question: Write short notes on randomized Algorithm.
0

Subject: Analysis Of Algorithm

Topic: Introduction To Analysis Of Algorithm

Difficulty: High

aoa(14) • 4.0k views
ADD COMMENTlink
modified 21 months ago by gravatar for awari.swati831 awari.swati831250 written 3.3 years ago by gravatar for satishmanje93 satishmanje9320
0
  1. Deterministic algorithm is an algorithm in which for given particular input it will always produce the same output, with the underlying machine always passing through the same sequence of states as shown in figure 1.

enter image description here

  1. To overcome the computation problem of exploitation of running time of a deterministic algorithm, randomized algorithm is used.
  2. Randomized algorithm uses uniform random bits also called as pseudo random number as an input to guides its behavior (Output).
  3. Randomized algorithms rely on the statistical properties of random numbers. One example of a randomized algorithm is quicksort.
  4. It tries to achieve good performance in the average case.
  5. Randomized algorithm is also called as probabilistic algorithm.
  6. Randomized algorithm flow steps is shown figure 2.

enter image description here

Example:

The problem of finding ‘a’ in an array of n elements:

In a given array of n elements let half elements are ‘a’ and that of half are ‘b’. One approach of the approach is to look at each element of the array and this is an expensive one and will take n/2 operations, if the array were ordered as ‘b’s first followed by ‘a’s. With this approach we cannot guarantee that the algorithm will complete quickly.

Using randomized algorithm, if we look randomly then we can find ‘a’ quickly with high probability.

Advantage of Randomized Algorithm:

  1. The algorithm is usually simple and easy to implement.
  2. The algorithm is fast with very high probability, and/or it produces optimum output with very high probability.

Uses:

Randomized algorithms are particularly useful when faced with a malicious attacker or “adversary”

ADD COMMENTlink
written 3.3 years ago by gravatar for satishmanje93 satishmanje9320
Please log in to add an answer.