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 (Page 1 of 5 )
In the previous part we covered the backtracking technique. Since that article was the first part of this series, I presented the fashion that will be followed throughout this multi-part series. Let me reiterate for a moment. Each article focuses on only one technique. First we present the theory that lies behind the concept, and then we solve any problems with it, explaining why and how it works.
Ready-to-run practical code snippets in ANSI C will be accompanied with examples written in pseudo-code, mostly because it depends on the programmer as to which language he or she s/he wants to use. Techniques, per se, are platform and language independent. Thus, we’ll opt for written English text and pseudo-code to explain the basics; the ANSI C snippets will make them seem more “code”-like.
If you missed the previous part discussing backtracking, I strongly suggest that you stop for a moment and read it right now. You are going to notice the differences between the “mentalities” of these two techniques much better if you already know backtracking. As you begin to grasp the concepts, you will see the contrast between them and you will also know when to rely on one or the other.
All of this being said, I invite you to join us for this educational ride.