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.
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.