Design & Analysis of Algorithms
105402Module 5: Tractable and Intractable Problems
Q1h. Hamiltonian path problem is ______? - (i) NP Problem - (ii) NP Complete - (iii) P Class Problem - (iv) N Class Problem20242m
Module 5: Tractable and Intractable Problems
View this question on its own page →Hamiltonian path problem is ______?
- (i) NP Problem
- (ii) NP Complete
- (iii) P Class Problem
- (iv) N Class Problem
Q1j. The choice of polynomial class has led to the development of an extensive theory called: - (i) computational complexity - (ii) time complexity - (iii) problem complexity - (iv) decision complexity20222m
Module 5: Tractable and Intractable Problems
View this question on its own page →The choice of polynomial class has led to the development of an extensive theory called:
- (i) computational complexity
- (ii) time complexity
- (iii) problem complexity
- (iv) decision complexity
Q5a. What is the relationship among P, NP and NP complete problems? Show with the help of a diagram.20197m
Module 5: Tractable and Intractable Problems
View this question on its own page →What is the relationship among P, NP and NP complete problems? Show with the help of a diagram.
Q5b. What are NP- hard and NP-complete problems?20247m
Module 5: Tractable and Intractable Problems
View this question on its own page →What are NP- hard and NP-complete problems?
Q8. Explain back-tracking, DFS and BFS with help of small example. Differentiate in between backtracking and dynamic programming. Apply the backtracking algorithm to solve the three-colouring problem for the following graph using state space tree. Assume three colours red, green and blue. 201914m
Module 5: Tractable and Intractable Problems
View this question on its own page →Explain back-tracking, DFS and BFS with help of small example. Differentiate in between backtracking and dynamic programming. Apply the backtracking algorithm to solve the three-colouring problem for the following graph using state space tree. Assume three colours red, green and blue.
Q8a. Define the classes P and NP.20232m
Module 5: Tractable and Intractable Problems
View this question on its own page →Define the classes and .
Q8b. Discuss what you mean by polynomial reduction.20232m
Module 5: Tractable and Intractable Problems
View this question on its own page →Discuss what you mean by polynomial reduction.
Q8c. Discuss diagrammatically the relation among P class, NP class, NP hard and NP complete.20232m
Module 5: Tractable and Intractable Problems
View this question on its own page →Discuss diagrammatically the relation among class, class, hard and complete.
Q8d. Describe Clique Decision Problem (CDP).20232m
Module 5: Tractable and Intractable Problems
View this question on its own page →Describe Clique Decision Problem (CDP).
Q9a. Write short notes on: Cook's Theorem20247m
Module 5: Tractable and Intractable Problems
View this question on its own page →Write short notes on: Cook's Theorem
- Install PocketlyBudget App•POCKETLY
Pocketly on Android
Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.
Q9b. Write short notes on: Branch and bound technique20197m
Module 5: Tractable and Intractable Problems
View this question on its own page →Write short notes on: Branch and bound technique
Q9b. Write short notes on: Approximation algorithms20227m
Module 5: Tractable and Intractable Problems
View this question on its own page →Write short notes on: Approximation algorithms