Design and Analysis of Algorithms
Selected Reading
- DAA - Discussion
- DAA - Useful Resources
- DAA - Quick Guide
- DAA - Hill Climbing Algorithm
- NP Hard & NP-Complete Classes
- DAA - Cook’s Theorem
- DAA - P and NP Class
- DAA - Vertex Cover
- DAA - Max Cliques
- Deterministic vs. Nondeterministic Computations
- DAA - Sublist Search
- DAA - Fibonacci Search
- DAA - Exponential Search
- DAA - Jump Search
- DAA - Interpolation Search
- DAA - Binary Search
- DAA - Linear Search
- Searching Techniques Introduction
- DAA - Radix Sort
- DAA - Counting Sort
- DAA - Bucket Sort
- DAA - Heap Sort
- DAA - Shell Sort
- DAA - Selection Sort
- DAA - Insertion Sort
- DAA - Bubble Sort
- DAA - Extract Method
- DAA - Heapify Method
- DAA - Insert Method
- DAA - Binary Heap
- Optimal Cost Binary Search Trees
- DAA - Multistage Graph
- DAA - Shortest Paths
- DAA - Spanning Tree
- Travelling Salesperson Approximation Algorithm
- Set Cover Problem
- Vertex Cover Problem
- Approximation Algorithms
- Fisher-Yates Shuffle
- Karger’s Minimum Cut
- Randomized Quick Sort
- Randomized Algorithms
- Travelling Salesman Problem | Dynamic Programming
- Longest Common Subsequence
- DAA - 0-1 Knapsack
- Floyd Warshall Algorithm
- Matrix Chain Multiplication
- DAA - Dynamic Programming
- DAA - Optimal Merge Pattern
- DAA - Job Sequencing with Deadline
- DAA - Fractional Knapsack
- Map Colouring Algorithm
- Dijkstra’s Shortest Path Algorithm
- Kruskal’s Minimal Spanning Tree
- Travelling Salesman Problem
- DAA - Greedy Method
- Towers of Hanoi
- Karatsuba Algorithm
- Strassen’s Matrix Multiplication
- DAA - Binary Search
- DAA - Merge Sort
- DAA - Max-Min Problem
- DAA - Divide & Conquer
- DAA - Space Complexities
- Master’s Theorem
- Time Complexity
- Asymptotic Notations & Apriori Analysis
- DAA - Methodology of Analysis
- DAA - Analysis of Algorithms
- DAA - Introduction
- Home
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
Deterministic vs. Nondeterministic Computations
Deterministic vs. Nondeterministic Computations
To understand class P and NP, first we should know the computational model. Hence, in this chapter we will discuss two important computational models.
Deterministic Computation and the Class P
The deterministic computation always provides the same output during the initial state with all the data available. As long as there is no change in the computation, there is no randomness involved with it.
There are various models available to perform deterministic computation −
Deterministic Turing Machine
One of these models is deterministic one-tape Turing machine. This machine consists of a finite state control, a read-write head and a two-way tape with infinite sequence.
Following is the schematic diagram of a deterministic one-tape Turing machine.
A program for a deterministic Turing machine specifies the following information −
A finite set of tape symbols (input symbols and a blank symbol)
A finite set of states
A transition function
In algorithmic analysis, if a problem is solvable in polynomial time by a deterministic one tape Turing machine, the problem belongs to P class.
Nondeterministic Computation and the Class NP
Nondeterministic Turing Machine
To solve the computational problem, another model is the Non-deterministic Turing Machine (NDTM). The structure of NDTM is similar to DTM, however here we have one additional module known as the guessing module, which is associated with one write-only head.
Following is the schematic diagram.
If the problem is solvable in polynomial time by a non-deterministic Turing machine, the problem belongs to NP class.
Advertisements