Deterministic and Non-Deterministic Algorithms
Deterministic and Non-Deterministic Algorithms differ in the way they produce outputs on multiple executions.
- 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.
- 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