Define and differentiate between deterministic and Non-deterministic algorithm. Write a non-deterministic algorithm to find the index of a maximum element in a list of n elements
Answers
In deterministic algorithm, for a given particular input, the computer will always produce the same output going through the same states but in case of non-deterministic algorithm, for the same input, the compiler may produce different output in different runs. In fact non-deterministic algorithms can’t solve the problem in polynomial time and can’t determine what is the next step. The non-deterministic algorithms can show different behaviors for the same input on different execution and there is a degree of randomness to it.
To implement a non-deterministic algorithm, we have a couple of languages like Prolog but these don’t have standard programming language operators and these operators are not a part of any standard programming languages.