5 More Decrease and Conquer Algorithms

S. Sridhar

Module 16

More Decrease and Conquer Algorithms

 

This module 16 focuses on an important design paradigm called decrease and conquer by variable factor algorithms. The Learning objectives of this

  • To explain Euclid Algorithm
  • To explain Interpolation Search
  • To explain Order statistics
  • To explain Deterministic Selection

Decrease and Conquer Design paradigm:

The decrease and conquer paradigm is based on problem reduction strategy. Problem reduction is a design strategy that aims to reduce a given problem to another problem with a reduced problem with smaller size. Then, attempts are made to solve the problem. Decrease and conquer is a design paradigm that uses the problem reduction strategy. It is also known as the incremental or inductive approach. As discussed earlier in the previous module, the steps of decrease and conquer is given as follows:

  1. Reduce problem instance to same problem with smaller Instance
  2. Solve problem of smaller instance
  3. Extend solution of smaller instance to obtain solution to original problem with larger instance

Thus, it can be seen that the logic involves the following steps:

  • Establish the relationship between problem of the given instance and its reduced instance of the smaller problem
  • Exploit this relation top-down or Bottom-up

Design and conquer design paradigm can be implemented using both top-down or bottom-up approach. Also, this design paradigm is known as inductive or incremental approach.

 

Type of Decrease and Conquer Strategy

Based on the decreasing factor, the decrease-and-conquer strategy can further be categorized into the following types:

  1. Decrease by a constant
  2. Decrease by a constant factor
  3. Decrease by a variable factor

Decrease by Variable Factor Method

One more category of the decrease-and-conquer algorithm is decrease by a variable factor. It can be observed that as the name implies, the decreasing factor varies. Some examples of the algorithms that belong to this category are interpolation search, selection, and deterministic selection algorithms.

 

Let us start the discussion on Euclid algorithm.

Euclid Algorithm

Euclid algorithm is one of the oldest algorithms designed by Euclid about 300 B.C. Euclid algorithm is useful to find the largest integer that divides both a and b. For example, GCD of two integers 36 and 24 , GCD(36,24) can be obtained using factoring method. Let us try , one of the standard method of finding GCD using factoring method: Factor a and b into primes and then choose the common ones:

 

–   24 = 2 x 2 x 2 x 3 and 36 = 2 x 2 x 3 x3

 

Hence, GCD of 36 and 24 can be obtained as 2 x 2 x 3 = 12. Factoring method takes a lot of time. Therefore, a recursive method based on Euclid method can be done as follows: Euclid’s algorithm is based on repeated application of equality

 

GCD(m, n) = GCD(n, m mod n)

 

It can be done as follows:

gcd(36, 24) = gcd(24, 36 mod 24)

=  gcd(24, 12)

=  gcd(12, 24 mod 12)

=  gcd(12,0)

=  12

 

The Iterative algorithm for finding GCD is given as follows:

Iterative form:

  1. Read two numbers x and y
  2. If y = 0, then return x as GCD
  3. Repeat While y is not zero, Divide x by y and set remainder to r

Change value of x to y Change value of y by r

 

The same algorithm can be done using recursive form as illustrated in the numerical example. The informal algorithm for finding GCD is given as follows:

 

Recursive form:

 

Euclid (x,y)

1. Input numbers x and y            2. if y == 0 return x

else

return Euclid(y, x mod y)

The formal algorithm for Euclid algorithm is as follows:

Algorithm Euclid(x,y)

%%  Input: x and y Begin

If (y == 0) return x

Else return Euclid(y, x mod y) End if

End.

Complexity Analysis:

What is the complexity analysis of Euclid algorithm? One can prove that the size, measured by the second number, decreases at least by half after two consecutive iterations. This, the complexity analysis of Euclid algorithm is T(n) Î O(log n) .

 

Interpolation Search

Interpolation search is another example of decrease and conquer by a variable factor. Interpolation search is faster than binary search. To illustrate this, let us consider the following scenario: Searching for the element 18 in an array, A = 12 13 14 16 18. The binary search for item 18 starts by finding the middle element 14. Then it proceeds. It can be observed that the idea of even split as in the case of binary search is not of much use here. On the contrary, if one searches from right to left, one can find easily the element 18.  The idea of interpolation search is to adopt a modified middle element finding. In the case of interpolation that is closer to the element to be searched. Therefore, interpolation search uses the approximate ‘middle point’, say C, which is a constant, for finding the target item.

This approximate middle element or constant C replaces the ‘exact mid’ of the binary search algorithm.

 

The informal Interpolation search is given as follows:

 

1.  Read array A and target key k

2.  Computer approximate middle

Here, k = key, low = first and high = last element

 

3.  Compare k with A[C] if equal return C else recurse . The formal algorithm is given as follows:

 

Algorithm IS(A[0..n-1], k )

 

%% Input: Array A and key k

 

%% Output: k if present, -1 if not present Begin

 

low ¬ 0;  high ¬ n-1

while low £ high do

if k = A[C] return C else if k < A[C]

 

call IS(A,l,C-1) else

 

call IS(A,C+1,r) End if

 

End While return -1 End

 

It can be observed that the interpolation search is similar to binary search except in finding the middle element.

 

Complexity Analysis

Interpolation search depends on the distribution of elements of an array. If the elements are distributed uniformly, then the complexity of the algorithm would be O(log(log n)) . On the other  hand, if the distribution is not uniform, the complexity of the algorithm is O(n). One can observe that for binary search, the complexity of the algorithm is O(log n) for all cases.

 

Order Statistics:

The problem of finding the kth smallest element in an unordered array is called selection or order statistics. Finding the smallest element in an ordered array is easy, as the first element of an array sorted in an increasing order is the minimum element and the last element is the maximum element. The brute force algorithm is given as follows:

  • Input: A set S of n elements and k
  • Output: The kth smallest element of S

step 1: Sort the n elements

step 2: Locate the kth element in the sorted list.

 

Complexity Analysis:

The time complexity is O(nlogn)

On the other hand, finding these in unordered array is difficult. So, these elements should be sorted first before finding minimum, maximum and median. Deterministic selection is linear finding of these statistics. Let us discuss the statistical terms now:

 

Minimum and maximum

In general, ith order statistic: ith smallest element of a set of n elements. The first order statistic is minimum and nth order statistic is maximum.

 

Median

 

Median is the “half-way point” of the set. When ‘n’ is odd, the median location can be obtained as follows: median = (n+1)/2. In n is even, then lower median, at = n/2 and upper median, at i = n/2+1. But lower medi an is always chosen for consistency. This is given as below:

Blum, Floyd, Pratt, Rivest, and Tarjan proposed a linear-order algorithm for finding the kth smallest element in a linear order without using the sorting procedure. This algorithm follows the decrease-and-conquer approach, as the strategy is to split the problem into subproblems and then select the appropriate subproblem for finding solutions. The procedure for selecting the kth smallest element in an unsorted array is given informally as follows:

It can be observed that the algorithm partitions the given array using a partitioning element. Then it finds the rank. The algorithm compares the expected kth element with the rank to get the appropriate subarray. Then the algorithm is used recursively till the target key is obtained. This concept is illustrated in the following Example 1.

Example 1: Find the element k = 3 and k = 7 using the above procedure.

 

Solution

As discussed earlier, the pivot element can be obtained using a partitioning procedure.   After partitioning, the pivot element is given as below:

 

 

 

Here, the number of elements less that pivotal element is Acount =3. As, Acount = k-1, return the pivot element 4 as the answer for k = 4.

 

For k = 7, count is greater than k – count -1, 7 – 3 -1 = 3rd element right subarray.

 

The process can be repeated on the right subarray. It can be found that the k = 7, is 7.

 

The formal algorithm is given as follows:

Algorithm Selection(A,k)

%% Input: k is the smallest item
Begin
Find pivot q
Aless = {All elements less than q}
Aequal = {q}
Agreater = { Elements greater than q}
Count = number of elements of Aless
If count = k-1, then return q
else If count > k-1, then
Selection(Aless,k) else
Selection(Agreater,k-count-1)
End if
End if
End

 

Complexity Analysis:

Each time when the pivot element partition the array exactly into two halves, the recurrence equation is  T(n)=T(n/2)+n, where n is required for separating the n elements into two sets. This T(n) =O(n), which is   the best case. However, in the worst case, the pivot element will be either the largest or the smallest element in the set. Thus, the array is partitioned into only one set of size n-1. Hence the recurrence  equation is, T(n)=T(n-1)+n, which is O(n^2)

 

Deterministic Selection

The informal algorithm for finding median using deterministic selection is given as follows:  Find Median problem – Deterministic Algorithm
Input: A set A of n distinct numbers and a number i, with 1 i  n.

Find median of medians:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

The formal segment of deterministic selection is given as follows

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Summary

  • In short, one can conclude as part of this module 16 that
  • Euclid algorithm uses decrease and conquer approach.
  • Interpolation search is effective than even binary search.
  • Selection algorithms finds smallest k in linear time.
  • Deterministic median algorithm finds median in linear time.

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.