Go backward to 3.12 Generic Algorithm Specialized by Strategy
Go up to 3 An Example of Concept Webs: Programming Concepts
Go forward to 3.14 Generic Divide-and-Conquer Sequence Algorithm
3.13 Generic Divide-and-Conquer Algorithm
A generic divide-and-conquer algorithm is a generic
algorithm whose steps are structured
according to the following strategy:
- Construct the output directly and return it, if the input is
simple enough. Otherwise:
- Divide the input into two or more (a finite number)
of smaller inputs.
- Recursively apply the algorithm to each of the smaller inputs
produced in the first step.
- Combine the outputs from the recursive applications to produce
the output corresponding to the original input.
This concept is one of many known ways of narrowing the generic
algorithm concept in terms of a strategy, which
gives a specific structure to the steps of the algorithm.
musser@cs.rpi.edu