7 Transform and Conquer Design paradigm

S. Sridhar

Module 17

Transform and Conquer Design paradigm

 

This module 17 focuses on an important design paradigm called Transform and Conquer design paradigm. The learning objectives of this module are

  • To explain basics of Transform and Conquer
  • To illustrate simple examples like presorting and unique elements
  • To understand matrix operations
  • To explain Gaussian Elimination

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. 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. This is illustrated through the following simple examples.

Consider the problem of multiplying two simple numbers XII and IV. These numbers are in Roman number system. As many are not comfortable with Roman number system, this gets transformed to another problem where Arabic numerals are used instead of Roman system.

  1. In the first stage, the numbers XII and IV is transformed to another problem of 12 X 4.
  2. In the second stage, the actual multiplication is done as 48, then the result is converted to Roman number as XLVIII.

Another good example of transform and conquer technique is finding LCM using GCD. For example, if GCD of two numbers is available, then LCM can be obtained as follows:

lcm (m, n) =                                                                     m ´(n   )

GCD  m, n

 

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. The illustrated example of roman number to Arabic number system is an example of instance simplification.
  • Representation Change is another variety where the strategy involves the transformation of an instance to a different representation. But this is done without affecting the instance. The illustrated example of roman number to Arabic number system is an example of instance simplification.
  • Problem reduction is a strategy that involves a transformation of a problem A to another type of problem B. It is assumed that the solution of problem B already exists. The illustrated example of reduction of computing LCM (Last Common Multiple) in terms of GCD is an example of problem reduction. s GCD. Hypothetically, let us assume that an algorithm exists only for GCD.

Presorting

Sorting an array before processing is called presorting. Presorting is helpful in various applications such as search and in finding element uniqueness.

 

Finding unique elements in an array

Consider a problem of finding element uniqueness in an array. The problem can be defined as follows: Example: Given a random list of numbers, determine if there are any duplicates.

 

Brute force Algorithm

A brute force algorithm involves checking ever pair of elements for duplicated. This means comparing an element with all other elements of an array. The informal brute force algorithm for element uniqueness is given as follows:

 

Algorithm Uniqueness

 

for each x Î A

 

for each y Î {A-x}

 

if x=y then

 

return not unique

 

endif

 

return unique

 

The complexity of this approach is q(n2).

 

Transform and Conquer approach

One can apply the principle of instance simplification here. One can sort the array instead. The advantage of sorting here is that only the adjacent elements to be checked. So the algorithm can be stated informally as follows:

  1. Sort the numbers.
  2. Check the adjacent numbers. If the numbers are same then return uniqueness as false.
  3. End.

The formal algorithm is given as follows:

 

Algorithm Elementuniqueness-Presorting(A[1..n])

 

%%   Input: Array A

 

%%   Output: Unique or not Begin

 

Sort A

 

for i = 1 to n-1

 

if A[i] = A[i+1] return not unique End for

 

return unique End

 

Complexity Analysis

 

Sorting requires q (n log n) time. The second step requires at most n-1 comparisons. Therefore,

 

the total complexity is q ( n )+q (n log n)

 

= q (n log n)

 

Search using Presorting

 

Presorting can be done for search also. The order in the array allows the usage of binary search.

 

The informal algorithm for binary search is given as follows:

 

Stage 1 Sort the array by Merge sort

 

Stage 2 Apply binary search

 

 

Complexity Analysis

Sorting requires q (n log n) time. The second step requires at most log(n) time. Therefore the

 

total complexity is q ( n )+q (n log n).

 

Therefore, the efficiency of the procedure is Θ(nlog n) + O(log n) = Θ(nlog n) Mode

 

Mode is defined as the element that occurs most often in a given array. For example, consider the following array of elements, A = [5, 1, 5, 5,5,7, 6, 5, 7,5] . The mode of array A is 5 as 5 is the most common element that appear most. If several and different values occur most often any of them can be considered the mode.

 

Brute force Algorithm

 

The brute force algorithm is to scan the array repeatedly to find the frequencies of all elements.

 

Informally, the frequency based approach is given below:

 

Step 1:  Find length of List A

 

max ¬ max(A)

 

Step 2:  Set freq[1..max] ¬ 0

 

Step3:    for each x Î A

 

freq[x] = freq[x] + 1

 

Step4:    mode ¬ freq[1]

 

Step 5:  for i ¬ 2 to max

 

if freq[i] > freq[mode]  mode ¬ i

 

Step6:    return mode

 

Complexity Analysis:

 

The complexity analysis of frequency based mode finding algorithm is q(n2).

 

Transform and conquer approach

Instead, the array can be sorted and run length of an element can be calculated on the sorted array. Informally, mode finding using presorting is given as follows:

  1. Sort the element of an array.
  2. Calculate the run length of an element
  3. Print the element having longest length
  4. Exit.

Formal algorithm based on [2] is given as follows:

Sort A

i ¬ 0

 

frequency ¬ 0

while i ≤ n-1

runlength ¬ 1;   runvalue ¬ A[i]

 

while i+runlength ≤ n-1 and A[i+runlength] = runvalue runlength = runlength + 1

 

if runlength > frequency

frequency ¬ runlength

modevalue ¬ runvalue

 

i = i + runlength

return modevalue

 

Complexity Analysis:

Sorting requires q (n log n) time. The finding of a run length requires only linear time as the array is already sorted. Therefore the worst case performance of the algorithm would be less than the brute-force method.

Matrix Operations

A matrix is a rectangular table of numbers. In scientific domain, matrices have many uses. Matrix addition and subtractions are relatively easy.

Most of the scientific applications use matrix operations like matrix inverse and matrix determinant. So there is a need to solve these problems. As the computational complexity of these algorithms are high, transform and conquer approach can be used. Gaussian elimination uses transform and conquer approach to solve set of equations. Additionally, it can be used to decompose matrices also. Matrix decomposition is useful for find inverse of a matrix and matrix determinant.

First let us discuss the method of Gaussian elimination in the subsequent section.

 

Gaussian elimination method

Solving an equation means finding the values of the unknown. A simplest equation is of the form:

 

Ax = y

 

A solution of this equation is x = y/A. but this is true only when (y ¹ 0 and A is not zero). All values of x satisfies the equation when y=0. This logic can be extended for two unknowns. Let us consider the following set of equations:

 

A11x + A12y = B1

 

A21x + A22y = B2

 

The equations can be solved first by finding x as

 

x = (B1 – A12y) / A11

 

Substituting this in the second equation gives y.

 

In general, if one plots these two equations as lines, then the intersection of two lines in a single point, then the system of linear equations has a unique solution. If the lines are parallel, then there is no solution. If the lines coincide, then there would be infinite number of solutions.

 

In many applications, one may have to solve ‘n’ equations with ‘n’ unknowns. The set of linear equations are as below:

 

A11x1 + A12x2 + … + A1nxn = B1

 

A21x1 + A22x2 + … + A2nxn = B2

…

 

An1x1 + An2x2 + … + Annxn = Bn

 

In matrix form, the above can be represented as

 

Ax = B

 

Gaussian elimination, names after Gauss, uses transform and conquer approach to transform this set of equations with ‘n’ unknowns

The transformation can be represented as follows:

 

Gaussian elimination aims to create a matrix with zeros in the lower triangle. This is called upper triangular matrix. This is done by elimination a variable at every stage in all equations. The advantage is that One can solve the last equation first, substitute into the second to last, and can proceed to solve the first one.

 

To do the manipulations, Gaussian elimination uses some elementary steps. The following elementary steps are used by Gaussian elimination.

  1. Exchanging two equations of the system

In this, two equations are exchanged. For example, consider the following equations.

 

x + y = 3

2x + y = 4

 

These equations can be exchanged as

 

2x + y = 4

X + y = 3

 

  1. Exchanging an equation with non-zero multiples

Say,

 

x + y = 2 can be replaced as

2x + 2y = 4.

 

  1. Replacing the multiple of one equation to another equation. For example, row 2, R2, can be expressed as a multiple of row 1, R1, and row 3, R3

 

The informal algorithm for Gaussian elimination is given as follows:

 

 

This illustrated in Example 1 [1].

 

Example 1

Solve the set of equations using Gaussian Elimination method

3x1 + x2 + x3    = 11

6x1 + 4x2 + x3  = 29

x1 + x2 + x3      =  7

 

In matrix notation, this can be written it as Ax = b. Augment the equation as below and apply the elementary operations as shown below:

2x2 – x3  = 7

         2x2  = 8

            x2 = 4

Using these two variables, the remaining variable can be obtained as follows:

 

3x1 + x2 + x3 = 11

         3x2 + 5 = 11

                   x2 = 11-5/3 = 6/3 = 2

 

 

 

Apply the elementary operation to reduce the augmented matrix to a triangular form called echelon matrix. So the idea is to keep a11 as pivot and eliminate all a11 in other equations. For example, in the second equation, a11 can be eliminated by the factor R2-(a21/a11). This operation is applied throughout the equation. Using the same logic, a11 is eliminated in all other equations. Similarly, using the multiple of (a31/a11), (a41/a11), …, (an1/a11), the matrix A can be reduced to a upper triangular matrix A’. Then, the solution can be obtained by back substitution. The algorithm for forward elimination is given as follows:

 

The backward substitution is given as follows:

 

 

Complexity Analysis

How many operations are required for Gaussian elimination? One division and n multiplication/division   is   required.    So    (n+1)    operations    for    (n-1)    rows,    requires (n -1)(n +1) = n2 -1 operations to eliminate the first column of matrix A. Similarly the second row involves (n -1)2 -1 operations. So all n rows, the numbers of operations are

So Gaussian elimination method time complexity is O(n3 ) .

 

Summary

In short, one can conclude as part of this module 17 that

  • Transform and Conquer is an effective design paradigm
  • Matrix operations are computationally very intensive
  • Gaussian elimination is an effective technique that uses transform and conquer method

 

References:

  1. S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.
  2. A.Levitin, Introduction to  the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.
  3. T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.