Divide and Conquer

(find constituent smaller problems)


Like Physics, the problems of the Universe can be described in smaller and smaller dimensions all the way down to the molecule and the atom

In solving algorithmic problems the underlying elements are not always immediately obvious

Divide the problem into parts until each sub-problem is manageable. Take those easily manageable parts and clobber them one at a time. Or continue dividing the ever smaller problems, until each is easily solvable.

You may remember the Greek mythological beast Hydra. Hydra was an impossible, multi-headed beast for humans to deal with. By burning each snake head, one at a time, Hercules (Heracles) won. It wasn't strength. He simply divided and conquered. [Image from: "Hydra (mythology)", Microsoft® Encarta® Online Encyclopedia 2001 http://encarta.msn.com © 1997-2001 Microsoft Corporation. All rights reserved.]


Every problem can be broken into three parts:

  • Input (generally what do you start with)
  • Processing
  • Output (what is the result?)
The processing part can be subdivided into smaller distinct steps**:

** "Divide and Conquer" should not be confused with "Successive or Stepwise Refinement". The former is a process in which a problem is divided into its component sub-problems, whereas in the latter the level of abstraction is repeatedly decreased by giving further explanation or more detail.



Last updated 2001/06/20
© J.A.N. Lee, 2000-2001.