Divide and Conquer Algorithm Technique - The Theory
(Page 2 of 5 )
The term divide-and-conquer is the literal translation of divide et impera coming from Latin. It originally referred to the political, military, and economic strategy often called divide ut imperes. Technically, it means that larger concentrations and groups ought to be divided (split) into smaller groups. This way their power can be decreased and the one implementing the strategy can overpower them successfully.
There has to be a correlation between the underlying idea in both military and computer science. But to answer this we should focus on the question of what kinds of problems can be solved using the divide-and-conquer algorithm. The problems I'm talking about can be divided into two or more sub-problems which are smaller in size, easier to solve, and ultimately can lead to the final solution.
Basically, if a problem can be divided into two or more sub-problems of the same (or related) type and ultimately each of these sub-problems' solution can be combined to find the final solution to the original problem, then divide and conquer can be used. It is especially important to emphasize that sub-problems should be of the same type or related. This is necessary because we use the same means of evaluation.
Additionally, we do not divide only the “big problem” into its sub-problems. We also divide the sub-problems and so on, until they become so simple that solving them directly becomes possible (trivial, if need be). We are going to know when the sub-problem becomes trivial because that’s when you can’t divide it anymore. So if you do get there, then you need to actually solve it.
In the first part of this series we used the tree-like analogy to see how the algorithm goes through the process of execution. Let’s see what happens if we apply that tree analogy to divide-and-conquer. Obviously, in the root node of the tree the original problem is located (this level is zero). Then this is divided into two or more sub-problems that are located on the first level of the tree, and so on.
In the end, the trivial sub-problems are located in the leaves of the tree (last node, without child(ren)). When the program gets there, those can be solved, and recursively relying on the recurrence relation, we can move further, solving the previous sub-problems and so on. This way we can eliminate each of the levels containing numerous sub-problems, moving closer to the root node, which is the original problem.
The divide-and-conquer approach has three major elements: divide, conquer, and combine. The first breaks a problem into sub-problems, the second solves a problem, and the latter combines the results coming from the previously solved sub-problems to get the final solution to the original problem.
Almost always we opt for a recursive approach based on a recurrence relation. In this case, the sub-problems are stored in the procedure call stack. However, there are exceptions where a non-iterative approach offers more flexibility and freedom regarding the place where we store the solutions of the sub-problems (stack, queue, etc.). We usually opt for this when the recursive variation doesn’t cut it (is too hard to implement).
Divide and marriage before conquest is a variation of the original divide-and-conquer technique. It essentially means that merging (combining) the sub-problems can be done right after each phase of division, not necessarily after we have solved all of the sub-problems. In these cases the combination of the solution(s) is already implemented in the recursion, so by the time we finish all of the sub-problems, the solution is ready. Sorting algorithms usually benefit from this variation of the original D&C.
Check out the following simplified D&C algorithm in pseudo-code. Pay attention to those three major segments of the algorithm (divide, solve, and combine). Glancing through a well-written, efficient, and optimal D&C algorithm, you can see its elegance.
procedure divide (general parameters)
if trivial then // condition of triviality
solve it
else // not trivial then
divide into sub-problems
solve them recursively // call this procedure until it becomes trivial
combine them to get the final solution
end if
end procedure
We are done with the theory. On the next page you are going to read a few problems solved with the divide-and-conquer algorithm. Get ready!
Next: Binary Searching Problem and Solution >>
More Development Cycles Articles
More By Barzan "Tony" Antal
/ 4 
