“Divide each difficulty into as many parts as is feasible and necessary to resolve it.”
-Rene Descarts
This quote aptly describes what is the logic and thinking behind divide and conquer !!
So join us in learning this very important concept, which will meet you again in the next post also!
Divide and Conquer is an algorithm design paradigm(generic model) that is based on Multi-branched Recursion(the problem is divided into sub problems and solved using recursion till base case is not hit).Typically, a divide and conquer algorithm works on these 3 steps:-
1.Divide : The given problem is divided into sub-problems.
2.Conquer : These problems are recursively solved.
3.Combine : Then the answers are combined as appropriate.
Hence , divide-and-conquer algorithm works by recursively decomposing a problem into 2 or more sub-problems of alike type, till they become simple. Once they are simplified and now combined to give the optimal solution to the question.
Let’s understand through a visual:-
Let’s understand through an example using merge sort:-
@bitxorbytes
Explanation
From the figure we can see that the problem (unsorted array) is divided into sub problems which are further divided into sub problems till the base case is not hit( single element in this case).Then the problem is conquered (sorted in order) and the results are combined to give the final solution (sorted array).
Thus,divide and conquer algorithm is explained.
Uses
The following algorithms are based on divide-and-conquer algorithm design paradigm −
- Merge Sort
- Quick Sort
- Binary Search
- Closest pair (points)
- Karatsuba algorithm for fast multiplication
- Strassen’s Matrix Multiplication
- Cooley–Tukey Fast Fourier Transform (FFT) algorithm
Advantages
Solving difficult problems
If a problem, can be decomposed into sub-problems , then solving them and combining the answers.
Algorithm efficiency
Divide and conquer algorithm is often used to discover /test for the efficiency of an algorithm.
Parallelism
Divide-and-conquer algorithms are naturally adapted for execution in multi-processor machines.
Memory access
Divide-and-conquer algorithms naturally tend to make efficient use of memory cache. The reason is that once a sub-problem is small enough, it and all its sub-problems can, in principle, be solved within the cache, without accessing the slower main memory.
Disadvantage
Recursion
Since divide and conquer uses recursion, it may lead program to be slow and if even a small error occurs ,it may lead to infinite loop.
Explicit stack
Usage of explicit stacks may make use of extra space,hence this leads to implementation issues.
Choosing the base cases
Base cases must be chosen wisely ,otherwise it may lead to infinite loop.
Sharing repeated sub-problems
There can be cases where the problem when broken down results in same sub-problems which may increases the solving time and extra space may be consumed.
We will be discussing some important algorithm based on this concept further in our blog, so stay tuned!
For any doubts or ambiguities, mail us at everythinggeeky.101@gmail.com
Don’t forget to Like, Comment and Share with your friends.
Stay Tuned for Everything Geeky.
See you next week!
Cheers!
Team Bitxorbytes
Follow us on insta @bitxorbytes
information credits: https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm
Cover Image credits: http://www.chess.com/article/view/how-to-set-up-a-chess-game
BitXorBytes 