Transformation of problems
In this chapter we consider ways to transform problems. Such transformations are critical in matching a problem to the characteristics of an algorithm. Sometimes the transformation is done implicitly by formulating the problem in a particular, perhaps non-obvious, way. In several of the examples in this book, however, we will first formulate the problem in what might be considered a “natural” way and then look for ways to transform the problem to allow an algorithm to be effective. We will see that problem transformation is one of the key elements in matching a problem to an effective algorithm.
For example, we can think of transforming:
(i) the variables or equations of a system of simultaneous equations, or