Transform and Conquer

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.