The decrease-and-conquer technique is based on exploiting the relationship between a solution to a given instance of a problem and a solution to its smaller instance.

**Decrease-and-Conquer**

*Plutarch says that Sertorius, in order to teach his
soldiers that perseverance and wit are better than brute force, had two horses
brought before them, and set two men to pull out their tails. One of the men
was a burly Hercules, who tugged and tugged, but all to no purpose; the other
was a sharp, weasel-faced tailor, who plucked one hair at a time, amidst roars
of laughter, and soon left the tail quite bare.*

—E.
Cobham Brewer, *Dictionary of Phrase and
Fable*, 1898

**T**he ** decrease-and-conquer** technique is
based on exploiting the relationship between a solution to a given instance of
a problem and a solution to its smaller instance. Once such a relationship is
established, it can be exploited either top down or bottom up. The former leads
naturally to a recursive implementa-tion, although, as one can see from several
examples in this chapter, an ultimate implementation may well be nonrecursive.
The bottom-up variation is usually implemented iteratively, starting with a
solution to the smallest instance of the

problem;
it is called sometimes the ** incremental approach**. There are
three major variations of decrease-and-conquer:

decrease
by a constant decrease by a constant factor variable size decrease

In the ** decrease-by-a-constant**
variation, the size of an instance is reduced by the same constant on each
iteration of the algorithm. Typically, this constant is equal to one (Figure
4.1), although other constant size reductions do happen occasionally.

Consider,
as an example, the exponentiation problem of computing ** a^{n}** where

or
“bottom up” by multiplying 1 by ** a n** times.
(Yes, it is the same as the brute-force algorithm, but we have come to it by a
different thought process.) More interesting examples of decrease-by-one
algorithms appear in Sections 4.1–4.3.

The ** decrease-by-a-constant-factor**
technique suggests reducing a problem instance by the same constant factor on
each iteration of the algorithm. In most applications, this constant factor is
equal to two. (Can you give an example of such an algorithm?) The
decrease-by-half idea is illustrated in Figure 4.2.

For an
example, let us revisit the exponentiation problem. If the instance of size ** n** is to compute

If we
compute ** a^{n}**
recursively according to formula (4.2) and measure the algo-rithm’s efficiency
by the number of multiplications, we should expect the algorithm to be in

A few
other examples of decrease-by-a-constant-factor algorithms are given in Section
4.4 and its exercises. Such algorithms are so efficient, however, that there
are few examples of this kind.

Finally,
in the ** variable-size-decrease** variety of decrease-and-conquer, the
size-reduction pattern varies from one iteration of an algorithm to another.
Eu-clid’s algorithm for computing the greatest common divisor provides a good
ex-ample of such a situation. Recall that this algorithm is based on the
formula

gcd** (m, n)** = gcd

Though
the value of the second argument is always smaller on the right-hand side than
on the left-hand side, it decreases neither by a constant nor by a constant
factor. A few other examples of such algorithms appear in Section 4.5.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Decrease and Conquer : Decrease and Conquer |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.