Transformation to a simpler or more convenient instance of the same problemâ€”we call it instance simplification.

**Transform and Conquer**

*Thatâ€™s
the secret to life . . . replace one worry with another.*

â€”Charles M. Schulz (1922â€“2000), American
cartoonist, the creator of *Peanuts*

This chapter deals with a group of design
methods that are based on the idea of transformation. We call this general
technique ** transform-and-conquer** because these methods work as two-stage
procedures. First, in the transformation stage, the problemâ€™s instance is
modified to be, for one reason or another, more amenable to solution. Then, in the second or
conquering stage, it is solved. There are three major variations of this idea
that differ by what we transform a given instance to (Figure 6.1):

Transformation to a simpler or more convenient
instance of the same problemâ€”we call it ** instance simplification**.

Transformation to a different representation of
the same instanceâ€”we call it ** representation change**.

Transformation to an instance of a different
problem for which an algorithm is already availableâ€”we call it ** problem
reduction**.

In the first three sections of this chapter, we
encounter examples of the instance-simplification variety. Section 6.1 deals with
the simple but fruitful idea of presorting. Many algorithmic problems are
easier to solve if their input is sorted. Of course, the benefits of sorting
should more than compensate for the

time spent on it; otherwise, we would be better
off dealing with an unsorted input directly. Section 6.2 introduces one of the
most important algorithms in applied mathematics: Gaussian elimination. This
algorithm solves a system of linear equations by first transforming it to
another system with a special property that makes finding a solution quite
easy. In Section 6.3, the ideas of instance simplification and representation
change are applied to search trees. The results are AVL trees and multiway
balanced search trees; of the latter we consider the simplest case, 2-3 trees.

Section 6.4 presents heaps and heapsort. Even
if you are already familiar with this important data structure and its
application to sorting, you can still benefit from looking at them in this new
light of transform-and-conquer design. In Section 6.5, we discuss Hornerâ€™s
rule, a remarkable algorithm for evaluating polynomials. If there were an
Algorithm Hall of Fame, Hornerâ€™s rule would be a serious candidate for
induction based on the algorithmâ€™s elegance and efficiency. We also consider
there two interesting algorithms for the exponentiation problem, both based on
the representation-change idea.

The chapter concludes with a review of several
applications of the third variety of transform-and-conquer: problem reduction.
This variety should be considered the most radical of the three: one problem is
reduced to another, i.e., transformed into an entirely different problem. This
is a very powerful idea, and it is extensively used in the complexity theory
(Chapter 11). Its application to designing practical algorithms is not trivial,
however. First, we need to identify a new problem into which the given problem
should be transformed. Then we must make sure that the transformation algorithm
followed by the algorithm for solving the new prob-lem is time efficient
compared to other algorithmic alternatives. Among several examples, we discuss
an important special case of ** mathematical modeling**, or expressing
a problem in terms of purely mathematical objects such as variables, functions,
and equations.

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

Introduction to the Design and Analysis of Algorithms : Transform and Conquer : Transform 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.