Non-Deterministic Algorithms in DAA

Learn about Non-Deterministic Algorithms in DAA, including definition, working principle, guessing and verification stages, comparison with deterministic algorithms, relationship with NP class, and examples like Hamiltonian Cycle and Vertex Cover.

Non-Deterministic Algorithms in DAA

Introduction

In a normal deterministic algorithm, the next step is uniquely determined at every stage of execution.
However, there are certain problems where multiple choices must be considered simultaneously to reach a solution.

The concept used to explain such problems is known as Non-Deterministic Algorithms.

What is a Non-Deterministic Algorithm?

A Non-Deterministic Algorithm is an algorithm in which:

• More than one option is available at each step
• The algorithm is assumed to automatically choose the correct option
• If any one execution path leads to a solution, the algorithm is considered successful

Such algorithms cannot be directly implemented on real computers and are therefore simulated using deterministic techniques.

Working Principle

A non-deterministic algorithm works in two conceptual stages:

1) Guessing Stage

• A possible solution is selected by guessing from all available options

2) Verification Stage

• The guessed solution is verified in polynomial time
• If the solution is correct, it is accepted; otherwise, it is rejected

Pseudo Code Format

NonDeterministic_Algorithm()
{
Select a candidate solution
if (solution is correct)
ACCEPT
else
REJECT
}

Deterministic vs Non-Deterministic Algorithms

Relationship with NP Class

• Non-deterministic algorithms are closely related to the NP complexity class
• NP = Nondeterministic Polynomial Time
• Problems in NP have solutions that can be verified in polynomial time

Examples

• Hamiltonian Cycle
• Vertex Cover
• Subset Sum
• Travelling Salesman Problem

Advantages of Non-Deterministic Algorithms

• Simplifies the analysis of complex problems
• Helps in understanding the nature of NP problems
• Clearly illustrates the limitations of algorithmic power

Limitations

• Cannot be directly implemented on real machines
• Simulation may require exponential time

Simulation of Non-Determinism

Non-deterministic behavior is simulated using:

• Backtracking
• Branch and Bound
• Parallel computation (conceptual model)

Conclusion

Non-Deterministic Algorithms are a theoretical concept that play a crucial role in understanding
Computational Intractability and the P vs NP problem.

Some More: 

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1