Home arrow Development Cycles arrow Page 5 - 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 - Taking a Break
(Page 5 of 5 )

We’ve come to the end of this segment. Throughout this article we covered the divide-and-conquer algorithm design paradigm. It is an especially important concept in computer science because solving problems with it can increase the overall efficiency, thus reducing complexity (sometimes from n^2 we can reduce it to n * log n). Additionally, its elegance should definitely be appreciated.

Here are a few conclusions regarding D&C. It is generally advisable to analyze the complexity of a D&C algorithm to see whether or not you gain efficiency. Most of the time, they lead to really efficient algorithms which work great on large numbers and so forth, but you may complicate things when only a very small amount of data will be worked with (perhaps the iterative approach would do better?).

Sometimes you can blend the divide-and-conquer algorithm paradigm with other techniques, but this is beyond the scope of this article. However, after you master all of the algorithm design techniques, you will find problems that can be solved using different paradigms, some yielding better results than others, but when you couple two or even more, that’s when you’d get the most out of them and write really good code.

There are lots of other examples of problems that are specifically suitable for solving with D&C; you can Google a few. These include such problems as Hanoi Tower, Koch Fractals, Karatsuba, Fibonacci Numbers, Matrix multiplication, Strassen’s Algorithm…

Have fun solving a few. Remember, only through practice do you “consolidate” the things you have learned. And the real deed is only done when you sit down in front of a computer, start up your IDE, write your code, compile, and bug-track (if need be).

Now we shouldn’t miss this perfect time to invite you to join our friendly ever-growing community of professionals, experts, and enthusiasts at DevHardware Forums. Our fields of interest include everything related to IT&C, basically hardware, software, and consumer electronics. You should also check out our sister site at Dev Shed Forums. Whatever questions you may debate, don’t be afraid to ask for help.


DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.

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