Non-Deterministic Algorithm

Non-Deterministic
Algorithm
Presented By:
Name: Divy Jain, Kalal Harsh
Roll No. : 19MCA054,19MCA058
Introduction of Non-Deterministic
Algorithm
In computer programming, a nondeterministic
algorithm is an algorithm that, even for the same input,
can exhibit in different behaviors on different runs, as
opposed to a deterministic algorithm.
There are several ways an algorithm may behave
differently from run to run. Such as concurrent
algorithm, probabilistic algorithm, non-deterministic
algorithm ,Deterministic algorithm.
What does Non-Deterministic Algorithm
mean ?
The algorithms in which the result of every algorithm
is not uniquely defined and result could be random are
known as the Non-Deterministic Algorithm.
A non-deterministic algorithm can provide different
outputs for the same input on different executions.
 A Deterministic algorithm which produces only a
single output for the same input even on different runs
and a non-deterministic algorithm travels in various
routes to arrive at the different outcomes.
Difference between Deterministic and
Non-deterministic Algorithms
Deterministic Algorithm Non-Deterministic Algorithm
 For a particular input the computer  For a particular input the computer
will give always same output. will give different output on different
execution.
 Example :  Example :
 Can solve the problem in polynomial  Can’t solve the problem in

time. polynomial time.
 Can determine the next step of  Can’t determine the next step of
execution. execution due to more than one path the
algorithm can take.
When we can use non-deterministic
algorithm and why ?
A nondeterministic algorithm are often used when the
problem solved by the algorithm inherently allows
multiple outcomes or when there is a single outcome
with multiple paths by which the outcome may be
discovered and each equally preferable.
 A Non-deterministic algorithms are useful for finding
approximate solutions and It is difficult to get an exact
solution and also expensive to derive using a
deterministic algorithm.
Phases of non-Deterministic Algorithm
When we can execution of non-deterministic algorithm
on a deterministic computer which has an unlimited
number of parallel processors. A non-deterministic
algorithm usually has two phases and output steps.
The first phase is the guessing phase, which makes use
of arbitrary characters to run the problem.
The second phase is the verifying phase, which
returns true or false for the chosen string.
 There are many problems which can be conceptualized
with help of non-deterministic algorithms including the
unresolved problem of P vs. NP in computing theory.
Non-deterministic Algorithm function
choice(X) :
chooses any value randomly from the set X.
failure() :
denotes the unsuccessful solution.
success() :
Solution is successful and current thread
terminates.
Non-deterministic Algorithm for this
problem
Problem statement :
Search an element x on A[1:n] where n>=1, on successful
search return j if a[j] is equals to x otherwise return 0.
j= choice(a, n)
if(A[j]==x) then
{
write(j);
success();
}
write(0); failure();
P vs. NP problem
The most notorious problem in theoretical computer science
remains open, but the attempts to solve it have led to profound
insights.
A mathematical expression that involves N’s and N2s and N’s
raised to other powers is called a polynomial, and that’s what the
“P” in “P = NP” stands for. P is the set of problems whose solution
times are proportional to polynomials involving N's.
An algorithm whose execution time is proportional to N3 is slower
than one whose execution time is proportional to N. But such
differences dwindle to insignificance compared to another
distinction, between polynomial expressions — where N is the
number being raised to a power — and expressions where a
number is raised to the Nth power, like, say, 2N.
If an algorithm whose execution time is proportional to
N takes a second to perform a computation involving
100 elements, an algorithm whose execution time is
proportional to N3 takes almost three hours. But an
algorithm whose execution time is proportional to 2N
takes 300 quintillion years. And that discrepancy gets
much, much worse the larger N grows.

Non-Deterministic Algorithm

Uploaded by

Copyright:

Available Formats

Non-Deterministic Algorithm

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Non-Deterministic Algorithm

Uploaded by

Copyright:

Available Formats

Non-Deterministic

 Can solve the problem in polynomial  Can’t solve the problem in

You might also like