Algo: Divide & Conquer Flashcards
1
Q
Explain Divide and Conquer in few lines
A
It’s an approach to solve a problem when input P is too big to solve in one go.
We divide the input P into K sub-input and solve the problem. Once solved, we combine output of K sub-input to arrive at the output for input P.
Divide and Conquer involves recursion.
2
Q
What kind of problems can be solved with Divide and Conquer?
A
- Binary Search
- Finding Maximum and Minimum
- Merge Sort
- Quick Sort
- Strassen’s Matrix multiplication
