Practice question · Select all that apply
Select every condition under which plain divide-and-conquer is the right tool.
Hints
- The pattern needs independent subproblems and a cheap combine.
- Overlapping subproblems and expensive combines are the two failure modes the lesson names.
Show the answer
- A. Each subproblem is a smaller version of the original
- C. The subproblem solutions combine cheaply
- E. The problem splits into independent subproblems of the same kind
Why
Divide-and-conquer wants independent, same-type, smaller subproblems that combine cheaply. Overlapping subproblems call for dynamic programming instead, and an expensive combine kills the speedup.
Practise Divide-and-Conquer Reasoning
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.