9 More Transform and Conquer Problems
S. Sridhar
This module 19 focuses on an important design paradigm called Transform and Conquer. This module discusses problems related to polynomial evaluation and faster exponentiation. The learning objectives of this module are
• To explain Transform and conquer variant representation change.
• To explain polynomial evaluation using Horner’s method.
• To explain faster exponentiation
• To problem reduction method
Transform and Conquer Design paradigm
Transform and conquer is a design paradigm where a given problem is transformed to another domain. This can be done for familiarity of simplicity [2,3]. The problem is solved in the new domain. Then, the solutions are converted back to the original domain. In short, transform and conquer proposes two stage solution
1. First stage involves the transformation to another problem that is more amenable for solution
2. Second stage involves solving the new problem where the transformed new problem is solved. Then the solutions are converted back to the original problem.
Variations of Transform and Conquer
Three variants of transform and conquer are as follows:
– Instance Simplification
– Representation Change
– Problem Reduction
Instance simplification is one variant where the problem transformed to the same problem of simpler or convenient instance.
Change of Representation
Change of representation is another useful variant of transform and conquer design paradigm. As part of this technique, two examples are discussed as part of the problem.
Polynomial Evaluation
One of the common problem is scientific domain is the evaluation of polynomial. A polynomial is given as follows:
Faster Exponentiation
Exponentiation is the problem of finding xn. The traditional algorithm for solving this is given below:
Algorithm Exp(x, n)
if n = 1 then
return x
else
return x ´ Exp(x,n-1)
end if
end
Complexity Analysis
What is the complexity of this algorithm? The complexity is O(n) as the algorithm requires (n-1) multiplications. If the exponent is large, the number of multiplications required would increase considerably. Therefore, a better solution can be provided for finding exponentiation using transform and conquer method.
Idea of Faster Exponentiation:
The concept of fast exponentiation was given in a Hindu literature Chandah Sutra in 200 BC.
x2 can be computed with one multiplication. If x4 needs to be computed, it can be computed as ( x2 )2 . In this case, only two multiplications are required instead of traditional four multiplications. Similarly, x8 can be computed as (( x2 ) 2 )2 with three multiplications. In general, the faster exponentiation can be done using log n computations.
The informal algorithm for computing is given as follows:
- Represent the exponent as a binary pattern P. Let the maximum number of bits be p.
- Scan the binary bits of pattern P.
bi =1: term = x * term
End case
End for
Return Product
End.
Complexity analysis:
The complexity of the algorithm depends on the binary representations of Therefore, the number of multiplications would be between ê log n ú and 2 ë 2 û
complexity of the algorithm is O(log n). the given number. êë log2 núû . Hence, the
Problem Reduction:
Problem reduction is another variant of this paradigm. Assume that there are two problems A and B. The problem A is unsolvable and problem B has an algorithm. Hence, the logic of problem reduction is the conversion of instance of problem A into instance of problem B using an algorithm. Then the problem A can be solved by invoking the problem solver of B as a subroutine. Then, the result can be converted back. Some of the examples of problem reduction are computation of LCM in terms of GCD, reducing game problems to graph search problems.
Summary
In short, one can conclude as part of this module 19 that
- Representation Change is an effective way to solve problems.
- Horner method uses representation Change.
- Faster exponentiation can be done using transform and conquer method.