Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Top-Down Algorithms: Divide-and-Conquer

In this section we discuss a top-down algorithmic paradigm called divide and conquer  . To solve a given problem, it is subdivided into one or more subproblems each of which is similar to the given problem. Each of the subproblems is solved independently. Finally, the solutions to the subproblems are combined in order to obtain the solution to the original problem.

Divide-and-conquer algorithms are often implemented using recursion. However, not all recursive methods are divide-and-conquer algorithms. Generally, the subproblems solved by a divide-and-conquer algorithm are non-overlapping.




next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.