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
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
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