Deterministic and Non-Deterministic Algorithms

Deterministic and Non-Deterministic Algorithms differ in the way they produce outputs on multiple executions.

Deterministic and Non-Deterministic Algorithms
Deterministic and Non-Deterministic Algorithms

Deterministic Algorithms

  • If we run deterministic algorithms multiple times on the same input, they produce the same result every time.
  • Deterministic algorithms are typically represented by the state machine, where the machine moves from one state to another state on a specific input.
  • The underlying machine always goes through the same states during execution.
  • Finding a random number is deterministic, it always returns a random number. Finding odd or even, sorting, finding max, etc. are deterministic. Most of the algorithms used in practice are deterministic in nature.

Non-deterministic Algorithms

  • The non-deterministic algorithm works on guessing. For some input, nondeterministic algorithms may produce different outcomes every time.
  • The nondeterministic algorithm operates in two phases: guessing and verification. After guessing the answer, the algorithm verifies its correctness.
  • In the non-deterministic algorithm, each state has a probability of a different outcome on the same input. The vending machine is an example of the deterministic approach, in which the outcome against given input is always deterministic.
  • Randomly picking some element from the list and checking if it is maximum is non-deterministic.
  • The nondeterministic algorithm operates in two stages.
  • Non-deterministic (guessing) stage : For input instance I, some solution string S is generated, which can be thought of as a solution.
  • Deterministic (verification) stage : I and S are given as input to the deterministic algorithm, which returns “Yes” if S is a solution for input instance I.
  • Non-deterministic algorithm behaves differently for the same input on different runs. The concurrent algorithm can produce different outputs for the same input on different runs due to the race condition.
  • Selecting random permutations of n numbers and checking the order of numbers is non-deterministic. The first permutation may be (1, 2, 3), next may be (3, 1, 2), next may be (2, 3, 1) etc.

Youtube Channel: https://shorturl.at/inryW

Leave a Reply

Your email address will not be published. Required fields are marked *