This paper reports on one such investigation into a class of related algorithms based on the principle of ‘divide and conquer’ We seek not only to gain a deeper but clearer understanding of the algorithms in this class, but to formalize this understanding for the purposes of algorithm design. The resulting theory may suggest strategies for designing objects in the class which have given characteristics.
Divide and conquer is perhaps the simplest program structuring technique which does not appear as an explicit control structure in current programming languages. Divide and conquer algorithms are common in programming, especially when processing structured data objects such as arrays, lists, and trees. The independence of subproblems means that they can be solved in parallel. Consequently, divide and conquer solutions to problems will become increasingly attractive with the advent of parallel architectures.
We chose to explore the synthesis of divide and conquer algorithms for several reasons:
- Structural simplicity
- Computational efficiency
- Parallel implementation
- Diversity of applications
Auto197