Home arrow Development Cycles arrow Page 2 - Divide and Conquer Algorithm Technique
DEVELOPMENT CYCLES

Divide and Conquer Algorithm Technique


This is the second segment of the multi-part series covering various algorithm design paradigms. As the title suggests, today our job is to present, discuss, and learn as much as we can, as briefly and clearly possible, about the divide-and-conquer algorithm technique. It is definitely an important concept in computer science and should be ready to be pulled out of every coderís toolbox.

Author Info:
By: Barzan "Tony" Antal
Rating: 5 stars5 stars5 stars5 stars5 stars / 20
September 23, 2008
TABLE OF CONTENTS:
  1. · Divide and Conquer Algorithm Technique
  2. · The Theory
  3. · Binary Searching Problem and Solution
  4. · Merge Sort Problem and Solution
  5. · Taking a Break

print this article
SEARCH DEVARTICLES

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!


blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials