Divide and Conquer Paradigm

Given a function to compute on n inputs, the divide and conquer strategy suggests splitting the input into k distinct subsets, where 1<k≤n, yielding k sub problems. These sub problems must be solved and then a solution must be found to combine the sub solutions into a solution of the whole problem. If the sub problems are relatively large, then the divide and conquer strategy can possibly be re-applied.

Often the sub problems resulting from a divide and conquer design are of the same type as the original problem. For those cases, the re-application of the divide and conquer principle is naturally expressed by a recursive algorithm. Now, smaller and smaller sub problems of the same kind are generated until eventually sub problems that are small enough to be solved without splitting are produced.

The Divide and Conquer paradigm involves 3 steps at each level of recursion.

1) Divide:

Divide the problem into a number of sub problem that are smaller instances of the same problem.

2) Conquer:

Conquer the sub problems by solving them recursively. If the sub problem sizes are small enough, however, just solve the sub problems in a straight forward manner.

3) Combine:

Combine the solutions of the sub problems into the solution for the original problem.

The following are some standard algorithms that follows divide and conquer paradigm:

I. Binary Search:

Binary search is a fast searching algorithm that searches an element in a sorted array. To perform binary search on an array sorted in ascending order first we have to calculate the middle index of the array, then the search element is searched in the middle of the array. If the element is smaller than the middle element, then binary search is performed on the left sub-array otherwise the binary search is performed on the right sub-array.

II. Merge Sort:

Merge sort is a sorting technique which is based on divide and conquer approach. Given a sequence of n elements a[1]…a[n], the general idea is to split them into two sets a[1]…

and

…a[n]. Each set is individually sorted and the resulting sorted sequences are merged to produce a single sorted sequence of n elements.

III. Quick Sort:

In quick sort, the division of an array into two sub arrays is made so that the sorted sub arrays do not need to be merged later. This is accomplished by re-arranging the elements in a[i:n] such that a[i]≤a[j] for all I between 1 to m and all j between m+1 to n, for some 1≤m≤n. Thus the elements in a[1:m] and a[m+1:n] can be independently sorted. No merge is needed.

The re-arrangement of the elements is accomplished by picking some element of a[], say t=a[s] and then re-ordering the other elements so that all the elements appearing before t in a[1:n] ≤t and all the elements appearing after t are greater than t. This re-arrangement is referred to as partitioning.

IV. Closest pair of points:

The problem is to find closest pair of points in a set of points in x-y plane. The problem can be solved in O(n²) time by calculating distance of every pair of points and comparing the distances to find the minimum. The divide and conquer algorithm solves the problem in O(nlogn) time.

Divide and Conquer Paradigm