Instance Simplification Method in Transform and Conquer Technique

Instance simplification is one of the Transform and Conquer techniques. To understand Instance Simplification, first let us understand what is transform and conquer.

Transform and Conquer is a technique whose main idea is to transfer the problem into some easier or similar versions using some procedure and then solve that easier or simpler versions and combine those versions to get the solution of the actual one. The design consists of two parts: 

• The first stage involves the transformation/breakdown of the complex problem into other problems that is simpler than the original one.
• The second stage involves solving the simpler problems and after the problem is solved the solutions are combined and converted back to get the solution of the original problem.

There are three ways to do that:

1. Instance simplification: a technique of simplifying the problem to more convenient or simpler instances.
2. Representation change: the data structure is transformed to represent the problem more efficiently.
3. Problem reduction: the problem can be transformed to an easier problem to solve

Example:

Let us understand the Instance simplification in a better way with the help of an example: 

Consider the problem of finding a unique element in a given array. 

Approach 1: To solve this problem, one can compare each element with all other elements and find out the unique elements. 

It can be written as follows:

• Traverse the entire array:
  • For each element, compare it with all other elements to check if it is present anywhere or not.
  • If another similar element is present, then report that the element is not unique.
  • Otherwise, that element is unique.

Algorithm:

Algorithm unique_element( A[1. . . n]:
        for i=1 to n-1
                temp = A[i]
                for j = i+1 to n:
                        temp1 = A[j]
                        if(temp == temp1) then
                                print ‘element is not unique’
                        end if
                end for
        end for

Time Complexity: O(N²) as the algorithm involves nested loops
Auxiliary Space: O(1)

Approach 2 (Instance Simplification): The above mentioned approach was complex in the sense of comparisons. It requires a lot of comparisons which can be reduced or converted to a simpler version as shown below. 

• To identify the unique element, one can first apply any sorting technique and sort all the elements. This step is called presorting. 
• The advantage of presorting here is that for further steps, only the adjacent elements will have to be checked, instead of looking for the element in the entire array.

This is the simplification of instance where there is lesser comparison for a single element.

The approach is as follows:

• Sort the array.
• Traverse the array:
  • For each element check if it is the same as its adjacent elements or not.
  • If that element is the same then that is not a unique element.
  • Otherwise, mark that as a unique element.

Algorithm:

Algorithm unique_element(A[1. . . n]):
        Sort (A[])
        for i = 1 to n – 1 
                temp = A[i]
                temp1 = A[i + 1]
                if(temp == temp1) then
                        print ‘element is not unique’
                end if
       end for

Complexity Analysis: 

• A quick sort type sorting algorithm takes O(N * logN) time. 
• Scanning of the adjacent element for checking uniqueness requires at most (N-1) comparisons i.e. O(N) time. 
• Therefore, the time complexity for the algorithm is the sum of these two steps. 
• Asymptotically, the time complexity is the maximum of {O(N), O(N * logN)} = O(N * logN).

Time Complexity: O(N * logN)
Auxiliary Space: O(1)

Thus the effectiveness of the algorithm is determined by the quality of the sorting algorithm used. Even though not much is gained in terms of time complexity, the advantage of this algorithm lies in the convenience of checking only the adjacent elements.  

Advantages: The advantages of the instance simplification method are mentioned below:

• Instance simplification is useful in simplifying array and matrix operations.
• It is used to make the instance simpler to solve. It is a type of breakdown of a complex task into easier subtasks. 
• Instance simplification also helps in the complex data manipulation to break complex data into a simpler architecture that makes data processing easy.
• Presorting is a common example of instance simplification. Presorting as the name suggests is sorting that is ahead of the time. It’s also a form of preconditioning which is a manipulation of the data to make the algorithm faster.