6 More Applications of Divide and Conquer

S. Sridhar

Module 14

More Applications of Divide and Conquer

 

This module 14 focuses on decrease and conquer paradigm. The Learning objectives of this module are as follows:

  • To understand decrease and conquer paradigm
  • To understand Insertion Sort
  • To understand topological Sort
  • To understand Permutations and Subsets
  • To know the algorithms for generation of Permutations and Subsets

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. This paradigm is useful for solving a variety of problems in the computer science domain.

 

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

For example, consider the following problem, of computation of an . The problem can be solved by reducing it another problem of a n = a ´ an-1 if n>0, If n =0, then its value is n. the problem can further be reduced. It can be observed that this design paradigm reduces a given problem size by a certain decreasing factor. Then it establishes a relationship between the solution to a given instance of the problem and that to a smaller instance of it. Once the relationship is established, it is exploited using the top-down (recursive) or bottom-up (iterative) approach to derive the final solution.

 

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 and Conquer by a constant:

In decrease by a constant variation, the problem size is reduced by a constant (mostly one) at every iteration. In this category, a problem of size n is divided into a subproblem of size ‘n − 1’ and an individual element n. This design paradigm then incorporates the individual element into the subproblem solution to obtain the final solution. The examples of this category are Insertion sort, Topological sort, generation of permutations and subsets. The steps of the decrease by a constant are as follows:

 

Step 1: Reduce a problem A of size n into a problem of size ‘n − 1’ and an individual element n.

Step 2: Solve the subproblem recursively or iteratively.

Step 3: Incorporate the individual element into the solution of the subproblem to obtain the solution of the given problem.

 

In decrease by a constant factor, a problem instance is reduced by a constant factor, which is 2 in most of the cases. The examples of this category are binary search, faster exponentiation, and Russian Peasant method for multiplying two numbers. In decrease by a variable factor, the reduction size varies from one iteration of the algorithm to another. The number of subproblems may also vary. The examples of this category are Euclid algorithm, selection by partition and Nim type games.

 

Decrease and conquer by a constant approach is discussed in the following sections.

 

Insertion Sort

Insertion sort is based on decrease and conquer design approach. Its essential approach is to take an array A[0..n-1] and reduces its instance by a factor of 1, Then the instance A[0..n-1] is reduced to A[0..n-2]. This process is repeated till the problem is reduced to a small problem enough to get solved.

 

The first element is initially considered to be a sorted element; therefore, the second element needs to be compared with one element, requiring only one comparison. The third element needs to be compared with the previous two elements. Thus, the logic of insertion sort is to take an element and copy it to a temporary location. Then the position is looked after for insertion. Once, a position is located, then the array is moved right and the element is inserted. This process is repeated till the entire array is sorted.

Informally the procedure is as follows:

  • Finding the element’s proper place
  • Making room for the inserted element (by shifting over other elements)
  • Inserting the element

Formal Algorithm

 

The formal insertion sort algorithm [2,3] is given below:

 

ALGORITHM InsertionSort(A[0..N-1])

 

for i = 1 to N-1 do

 

temp = A[i]

 

j = i-1

 

while j ≥ 0 and A[j] > temp do

 

A[j+1] < A[j]

 

j = j-1

 

A[j+1] = temp

 

This procedure is illustrated in the following numerical example.

 

Example 1: Apply quicksort to the following set of numbers and show the intermediate result.

Solution:

 

As discussed earlier, the first number is considered as a sorted number. Then one by one elements are inserted into its appropriate position, and the length of the sorted list is increased. This process is continued till all the elements are sorted.

  • 88 | 43 68 92 23 34 11
  • 43 88 | 68 92 23 34 11
  • 43 68 88 | 92 23 34 11
  • 43 68 88 92 | 23 34 11
  • 23 43 68 88 92 | 34 11
  • 23 34 43 68 88 92 | 11

The final sorted list is : 11 23 34 43 68 88 92

 

Complexity Analysis:

The basic operation of this algorithm is a comparison operation. The number of comparisons depends on the nature of inputs. As said earlier, The first element is initially  considered to be a  sorted element; therefore, the second element needs to be compared with one element, requiring  only one comparison. The third element needs to be compared with the previous two elements. Worst case analysis: The worst-case complexity analysis of insertion sort can be determined as

 

follows: Hence, this requires two comparisons. Thus, in general, for n elements, the number of

 

comparisons would be as follows:

 

 

Best-case complexity analysis The best-case complexity of insertion sort occurs when the list is in a sorted order. Even in this case one comparison is required, to compare an item with its previous element. Thus, at least n − 1 comparisons are required. Therefore, the complexity analysis of insertion sort in best case would be

 

Therefore, the complexity of the algorithm is O(n). In addition, no shifting of data is required and space requirement for the sort is n. Similarly, the average case complexity of insertion sort is   O (n2 )

 

Topological Sort

Topological sort is one of the most important sorting used in variety of applications such as course prerequisites and project management. Thus, the objective of topological sort is to produce an ordering that implies a partial ordering on the elements. Thus, the ordering of the elements satisfies the given constraints. First, given a set of constraints graph is constructed. Every vertex represents an item. Every constraint is represented as an edge. For example, the constraint where item A must finish before B, then a directed edge is created from A to B. If the edge is represented as <A,B>, then the vertex A appears before vertex B in the linear ordering list.

 

Topological sort is performed for directed acyclic graphs (DAGs), and it aims to arrange the vertices of a given DAG in a linear order. Thus, a DAG is an essential and necessary condition for topological sort. What is a DAG? A DAG has no path that starts and ends at the same vertex. A sample DAG is shown below in Fig. 1.0

Fig. 1.0: A sample DAG

Recollect that a node of a graph that has no incoming edge is called a source and a vertex that has no outgoing edge is called a sink. A DAG has only one source and one sink. If a graph has many sources, then one can create a super source by creating a node and connecting it to all source nodes.

 

Topological Sort using DFS

Topological sorting can be performed using BFS and DFS algorithms. The following is the informal algorithm for performing topological sort using DFS [2,3]:

  1. Perform DFS traversal, noting the order of the vertices that are popped off stack
  2. Reverse order solves topological sorting problem

In other words, the finish time F(u) of all the vertices of a graph is obtained. Then a queue Q is created and all the vertices are inserted on to the queue Q based on finish time. Then the contents of the queue is printed as the sorted sequence.

 

Formal Algorithm

The formal algorithm for Topological sort is given as follows:Topological-

 

Sort()

 

Begin

 

Run DFS

 

When a vertex is finished, output it and assign a number

 

Vertices are output in reverse topological order

 

End.

 

It can be used on the following problem. Consider the following graph shown in Fig 2.

Fig 2: Initial Graph

 

Initially A is visited. Then the verted D is visited. Then, vertex E is visited. Then, vertex F is visited. Finally, vertex H is visited. This is numbered as 5. By reversing the DFS traversal, it can be observed that F is numbered as 4, vertex E is 3, vertex D is numbered as 2 and finally vertex A as 1. By reversing this one get the topological order which is given as A D E F H.

 

Topological ordering using source node removal algorithm

In source node removal algorithm, one has to identify the source repeatedly and it is removed. Simultaneously, all the edges incident to it are removed. This process is repeated till either no vertex is left or there is no source among remaining vertices left. As an example, consider the following graph shown in Fig. 3. This represents the prerequisites of a set of courses that needs to be taken.

 

Fig. 3. : Example course graph

 

It can be observed, the node that has no incoming edges is C1. Therefore, it is removed along with its incident edges. Then, C3 is the vertex that is source. Then, it is removed. Then C4 is the vertex , that is source and hence removed. Finally, the node c5 is selected. Therefore, the sorting order is given as follows: C1, C3, C4 and C5.

 

Complexity Analysis

Let there be m vertices and n edges of a graph. Then the topological algorithm takes O(m) time for picking the vertex that has no incoming edges. This is done by examining the corresponding adjacency matrix or adjacency list. Picking the vertex after identification takes a constant time. Deleting the vertex along with its edges takes O(n) time. Putting together, the algorithm takes O(m + n) time.

 

Permutations

Permutation is an arrangement of objects in a linear order. A permutation of a set of objects is a particular ordering of those objects For example, for three objects A, B and C, the first element  A can be arranged in three ways, the second object B in two ways, and the third object C in one way. Thus, the three objects can be arranged in 3! Ways. Therefore, the permutations are {ABC, ACB, BAC, BCA, CAB, CBA}. Each arrangement is called a permutation. In general, there are n! ways of arranging a set of n elements.

Generating a permutation may seem to be a trivial task. However, in reality, it is not so. For example, if there are 100 elements, then there are 100! ways of arranging the elements. Therefore, there is a need for generating permutations in an effective manner.

 

Decrease and Conquer Approach:

Decrease-and-conquer paradigm is used for permutation generation. In order to generate n! permutations using the decrease-and-conquer paradigm. For example, consider the problem of generating permutations for the set {A,B,C}.

 

The solution using the decrease-and-conquer paradigm can be given as follows:

 

The problem of permutation of three elements P is reduced to the subproblem(P¢) of generating permutation of two elements {A,B}. Then, this problem is reduced to the problem of generating permutation of subproblem {A}.The permutation of {A} is {A}. Then, the element {B} is introduced to enlarge the solution. Then the element {A} is added to get the final answer.

 

Informal Algorithm

 

To find all permutations of n objects:

 

Find all permutations of n-1 of those objects

Insert the remaining object into all possible positions of each permutation of n-1 objects

 

This can be illustrated as follows:

 

This process is described as follows:

 

Given the empty set { }, the only possible permutation is { }

 

Given the set {A}, the only possible permutation is {A}

 

Given the set {A, B}, the possible permutations are

 

{AB, BA}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Johnston–Trotter Algorithm

Another way of generating permutations is by using the Johnston–Trotter algorithm that uses the decrease-and-conquer strategy. This algorithm generates permutations in a non-lexicographical order. In this algorithm, every integer is associated with a direction. For example, <3 means the integer 3 is assigned a direction left and >3 means it is assigned a direction right. The core idea of this algorithm is that, a integer is called a mobile integer if it points to a neighbouring integer than is lesser than it. For example, in the generation of a permutation like <2 <3 <1, 3 is a mobile integer as it is pointing to an integer that is lesser than it. The right- and left-most columns of a list are called its boundaries. If any mobile integer in a boundary does not point to any integer, then the number is not a mobile number. In the generated sequence <3 <2 <1, 3 is no longer a mobile number as it is in the left-most column (or boundary).

 

Informally, the Johnston–Trotter algorithm is given as follows:

 

ALGORITHM Johnson Trotter (n)

 

Initialize the first permutation with 1 2 … n

 

while there exists a mobile integer k do

 

find k – the largest mobile integer

 

swap k and the adjacent integer pointed by arrow reverse the direction of all integers that are larger than k

 

This algorithm for generating permutations for three elements {1,2,3} is given below in Table 1.:

 

Table 1. Generating permutations for three elements using the Johnston–Trotter algorithm

Permutations Descriptions
<1 <2 <3 3 is the mobile integer as it points to ‘2’ that is smaller. Therefore, move the mobile integer.
<1 <3 <2 Now the mobile integer is pointing to ‘1’, which is smaller. Therefore, move it
<3 <1 <2 The mobile integer 3 has reached the boundary and does not point to any element. Therefore, look for the next largest integer, which in this case is ‘2’. Move it to get the next permutation and also change the direction of the integers that are larger than the current mobile integer.
3> <2 <1 It can be observed that the direction of 3 is changed. In other words, 3 has become a mobile integer again. Now move it again.
<2 3> <1 Now the mobile integer 3 points to a smaller number ‘1’. Therefore, move it again.
<2 <1 3> The numbers 2 and 3 have reached the boundaries and do not point to any integers that are lesser than these. As there are no mobile integers, exit.

Generating Subsets

The following are the important terminologies related to this problem:

 

Set : A collection of distinct elements. For example = colour = { red, Blue, Green}

Subset : A set B is a subset of A , if its all elements are in A. For example, A = {1,2}, then the subsets of A are { }. {1}, {2}, {1,2}

Power set: The set of all subsets is called power set

Generating Subsets Using Decrease-and-conquer Strategy

 

To generate subsets A = {a1, a2, a3, …, an,}, one has to divide this into two groups: S1 = {a1, a2, a3, …, an−1} and S2 = {an}. Add an to each subset of S1 to get the final solution. Example:

{1,2}

 

reduce this problem to

 

{1}

 

reduce this problem to

 

{}

 

So the solution is

 

{}

 

{1} {} after {1} is inserted

 

{1, 2} {2} {1} {}

Another easy approach to generate subsets is to use a binary string for n digits. The idea is to have a 1:1 correspondence between a binary string and the generation of subsets. Informal algorithm based on [1] is given as follows:

  1. Initialize the counter i to 2n −1
  2. Initialize the item counter j = number of items
  3. Extract the jth bit from the counter. If binary digit is 1, then include the item , otherwise, exclude it
  4. Print the subsets.

The following Table 2 summarizes the generation of the subsets.

 

Table 2: Generation of Subsets

 

Table 1: Generation of Subsets Informally, the algorithm for generation of subsets [1,2] is given as follows:

Step 1: For n elements represent sets with an n-bit string.

Step 2: For each bit of the n-bit string, perform the following operation:

Thus, the algorithm for generating subsets becomes a sort of a counting algorithm. Informally, the
Step 3: Print the resulting subsets 0 → 2n−1, which represents the power set of n elements. Thus, the algorithm for generating subsets becomes a sort of a counting algorithm. Informally, the counting can be said as follows:

 

Complexity Analysis

 

The complexity analysis is O(n 2n ).

 

Summary

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

  • Decrease and conquer guarantee solution and effective.
  • Insertion sort and Topological sort are important problems and can be solved by decrease and conquer strategy.
  • Generating Permutations and subsets are important problems that can be solved effectively using decrease and conquer strategy.

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.