DECREASE & CONQUER

DECREASE & CONQUER

Description:

Decrease & conquer is a general algorithm design strategy based on exploiting the relationship between a solution to a given instance of a problem and a solution to a smaller instance of the same problem. The exploitation can be either top-down (recursive) or bottom-up (non-recursive).

The major variations of decrease and conquer are

1. Decrease by a constant :(usually by 1):

a. insertion sort

b. graph traversal algorithms (DFS and BFS)

c. topological sorting

d. algorithms for generating permutations, subsets

2. Decrease by a constant factor (usually by half)

a. binary search and bisection method

3. Variable size decrease

a. Euclid’s algorithm

Following diagram shows the major variations of decrease & conquer approach.

Decrease by a constant :(usually by 1):

clip_image002

Decrease by a constant factor (usually by half)

clip_image004

Comments

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

Drawing Trees:HV-Layout