Non- Deterministic Algorithms

Non- Deterministic Algorithms

1. Non-Deterministic Algorithms Name: Dipankar Boruah Roll no: MCA/21/24

2. Content: Introduction Deterministic algorithm Non-deterministic algorithm Stages of Non-deterministic algorithm Non-deterministic Search Algorithm Non-deterministic Sorting Algorithm Functions used in the Algorithm

3. Introduction Two types of algorithm: Deterministic and Non-deterministic. An algorithm which provides different output for same input is a non-deterministic algorithm.

4. Deterministic Algorithm: Particular input will always produce the same output. Purely determines its input where no randomness is involve. It is uniquely defined without any ambiguity. Has predefined output. q q 1 q 2 1 Fig:1

5. Non-deterministic Algorithm May not have unique results. There can be specific set of possibilities for each operation. It is a two stage algorithm (Guessing and Verification). No particular rule is followed here to make the guess. q q 1 q 2 q 3 Fig:2

6. Stages of Non-deterministic algorithm Non-deterministic Stage or guessing stage. Deterministic Stage or verification stage.

7. Non-deterministic Stage(Guessing stage) Here it generate an arbitrary string that can be thought of as a candidate solution.

8. Deterministic Stage(Verification stage) In this stage we take candidate solution and instance of the problem as the input. It returns yes if the candidate represent the actual solution(if the guessing is correct). If the answer is no our guessing is wrong.

9. Non-deterministic Algorithm A Non-deterministic Algorithm terminates if and only if there exist no set of choices leading to a successful signal. A machine that is capable of executing a Non-deterministic Algorithm is called as Non-deterministic machine, Non-deterministic finite automata(NFA).

10. Non-deterministic Search Algorithm No looping so, c omplexity = O(1) Searching x on A[1:n], on success returns j if A[j]=x or return 0 otherwise j = choice(1,n); //j will return a arbitrary value form 1 to n if (A[j]==x) then {write(j ); success();} /*if we find the search item x in jth location then write() will write the value of j in output and success() will indicate successful completion.*/ write(0); Failure(); // will indicate failure

11. Non-deterministic Sorting Algorithm No nested loops so, complexity = O(n) Sorting array A[1:n] of positive integers in ascending order Algorithm Nsort ( A,n ) // sort n positive integers. { for i =1 to n do B[ i ]=0; // Initialize B [] with all location 0 for i = 1 to n do //Searching in the main array { j = choice(1,n ); //j will return a value form 1 to n if(B[j]!=0)then failure (); B[j] = A[ i ]; //Taking a value from A[ i ] and putting it in B[j] th location } for i =1 to (n-1)do // verify order if (B[ i ]>B[i+1]) then failure (); //if the items are not in ascending order will fail write(B[1:n ]); //will print the sorted array success (); //indicate successful termination. }

12. Functions used in the Algorithm Choice(s)- it randomly chooses one of the elements of set(s) Failure()- it signals an unsuccessful completion. Success()- it signals a successful completion.

13. Uses In a Np -problem the algorithm having non-polynomial time complexity, by applying non-deterministic algorithm on them, the complexity might get reduce and it can come to polynomial time.

14. Reference: https:// www.techopedia.com/definition/18830/deterministic-algorithm https:// www.geeksforgeeks.org/difference-between-deterministic-and-non-deterministic-algorithms https:// en.wikipedia.org/wiki/Nondeterministic_algorithm https:// www.youtube.com/watch?v=ZNe1ziMExGg https:// www.tutorialspoint.com/difference-between-deterministic-and-non-deterministic-algorithms

15. THANK YOU