Which of the following problems CANNOT be solved by using divide and conquer…
2022
Which of the following problems CANNOT be solved by using divide and conquer algorithm?
- A.
Merge sort
- B.
Binary search
- C.
0-1 knapsack
- D.
Compute binomial coefficient nCk
Attempted by 82 students.
Show answer & explanation
Correct answer: C
Divide and conquer applies to Merge Sort, Binary Search, and Binomial Coefficients as they have independent subproblems. The 0-1 Knapsack problem requires Dynamic Programming because it has overlapping subproblems.