McqMate

Q. |
## A non-deterministic algorithm is said to be non-deterministic polynomial if the time- efficiency of its verification stage is polynomial. |

A. | true |

B. | false |

Answer» A. true | |

Explanation: one of the properties of np class problems states that a non-deterministic algorithm is said to be non-deterministic polynomial if the time-efficiency of its verification stage is polynomial. |

3.7k

0

Do you find this helpful?

25

View all MCQs in

Design and Analysis of AlgorithmsNo comments yet

- The worst-case efficiency of solving a problem in polynomial time is?
- The running time of Bellmann Ford algorithm is lower than that of Dijkstra’s Algorithm.
- Problems that can be solved in polynomial time are known as?
- Which algorithm is the most efficient numerical algorithm to obtain lcm?
- Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm.
- Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.
- Dijikstra’s Algorithm is more efficient than Bellmann Ford Algorithm.
- Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?
- Dinic’s algorithm runs faster than the Ford-Fulkerson algorithm.
- What is the efficiency of Gale-Shapley algorithm used in stable marriage problem?