Podcast
Questions and Answers
Which group of problems has solution times bound by a polynomial of a small degree?
Which group of problems has solution times bound by a polynomial of a small degree?
- Group-3
- Group-2
- Group-4
- Group-1 (correct)
Which problem is an example of a Group-1 problem with a polynomial time algorithm?
Which problem is an example of a Group-1 problem with a polynomial time algorithm?
- Knapsack ($O(2^{n/2})$)
- Ordered Search ($O( ext{log}n)$) (correct)
- Polynomial evaluation ($O(n)$)
- Traveling Sales Person ($O(n^2 2^n)$)
Which group of problems has solution times not bound by a polynomial?
Which group of problems has solution times not bound by a polynomial?
- Group-4
- Group-2 (correct)
- Group-3
- Group-1
Which problem is an example of a Group-2 problem with a non-polynomial solution time?
Which problem is an example of a Group-2 problem with a non-polynomial solution time?
Why is it important to find algorithms with computing times greater than polynomial very quickly?
Why is it important to find algorithms with computing times greater than polynomial very quickly?
Define NP and explain the two groups of problems based on their solution times.
Define NP and explain the two groups of problems based on their solution times.
Give an example of a problem in Group-1 with a polynomial time algorithm and its time complexity.
Give an example of a problem in Group-1 with a polynomial time algorithm and its time complexity.
Provide an example of a problem in Group-II with a non-polynomial solution time and its time complexity.
Provide an example of a problem in Group-II with a non-polynomial solution time and its time complexity.
Why is it challenging to develop a polynomial time algorithm for any problem in Group-II?
Why is it challenging to develop a polynomial time algorithm for any problem in Group-II?
Why is it important to find algorithms with computing times greater than polynomial very quickly?
Why is it important to find algorithms with computing times greater than polynomial very quickly?