Divide And Conquer

A common ProblemSolvingHeuristic in which the problem is split into two or more smaller problems which are solved separately. Often, these sub-problems can further be divided until solving each one is trivial. The sub-solutions are then combined to generate the solution to the original problem.

Anyone got a more technical definition?

I'd emphasize that you can recursively use the same algorithm on the smaller problems. As the definition above reads, it leaves open the possibility that you can first divide a problem and then apply a different algorithm to those smaller problems.

Actually, the same algorithm is typically not applied all the way down to the base case. For example with quicksort once you get down to 2 elements, you do not recursively apply quicksort. Or with efficient matrix multiplication, once your matrices are broken down to small (say 2x2) matrices, you use some other very efficient method to multiply them. (This is how matrix multiplication got down under O(n^3): Strassen figured out how to multiply 2 2x2 matrices using 7 multiplications instead of 8.) This is typical in the analysis of algorithms, and in the subsequent implementation. The analysis results in a recurrence relation with a known base case. The base case is solved using special purpose knowledge / code, not the logic that "solves" the bigger cases (by dividing them).

I think there may be a misconception here. The reason Strassen's trick leads to an o(n^3) algorithm is that you use the 7-multiplication 2x2 matmult at every node in the tree, not just at the leaves. In fact, once your matrices get small enough you would certainly not use the 7-multiplication method, because it involves a larger number of additions and subtractions.

Also of interest, possibly, is the MultiplyAndSurrender approach, described in a very amusing SIGACT article in 1984 by A Broder and J Stolfi

DivideAndConquer is more general than just algorithms. There's no need to restrict it to using the same recursive algorithm. DivideAndConquer applies to such things as war and capitalism, for instance, where the notion of 'algorithm' is pretty much moot.

DivideAndConquer may not always result in a correct solution, especially for VeryLargeScale? systems -- when the inter-relationships between the subdivided components becomes sufficiently complex. In this case, the MetaModel comprised of the components must itself be scrutinized as a separate problem. --KirkKitchen

DivideAndConquer is often misapplied in organizational situations. The application results from the fallacious belief that if you break an organization into several pieces, and ask each piece to do its part of the whole job as well as it can, those requests will automatically result in the whole job being done well.

Sometimes, it results in the whole job being done very poorly. For example, I once heard about an engineer in a large electronics manufacturing company who developed a chip set that would reduce the cost of making a color TV set by a factor of two. The company ultimately refused to use the new chip set in its own products, because it had no second source.

In this example, the people who decided that all critical components must be multiple sourced were merely trying to minimize the risk to which their actions directly exposed the company. They didn't care about risks of inaction, as those risks would fall on other organizations rather than on them.

I am looking for a good name for this phenomenon. The best I've found so far is DivideAndBotch?. Other suggestions are welcome.

BirthInThreeMonths?: If you get 3 women instead of one to work on the job of carrying a baby, then you can give birth after only 3 months instead of the usual 9.

--AndrewKoenig

Hmm, I'm on your wavelength. How about DivideAndFalter? (has same meter and sorta rhymes), DivideAndSurrender?, DivideAndRetreat?. MultiplyAndSurrender might be relevant.

Let's not forget DynamicProgramming as another technique where DivideAndConquer fails in algorithm design. -- RobertField

Still, as a heuristic, DivideAndConquer is very general and often very powerful.

As a simple example, DivideAndConquer is an excellent meta-debugging technique. Imagine you have a large legacy function that is screwing up somewhere, and the only debugging tool you have is print statements. The naive approach is to spend 20 minutes putting in 100 print statements. The DivideAndConquer approach is to put one print statement in the middle of the function and test to see if the code reaches it. If it doesn't, put another print halfway between the beginning and the middle. If it does, put the next print halfway between the middle and the end. Repeat until the section you've narrowed it down to is small enough that you can put print statements between each line. Total time: 3-5 minutes depending on the length of the modify-compile-run cycle.

Even if you have more modern debugging tools, you can often apply DivideAndConquer with those (hence meta-debugging). For example, you could replace print statements with breakpoints in the above example. Sometimes, especially with LegacyCode, I'll resort to commenting out huge chunks of code in an effort to locate a bug via DivideAndConquer. This is surprisingly effective.

BinarySearch is a good example of DivideAndConquer

But see RefactorLowHangingFruit and ConquerAndDivide

CategoryRefactoring