Divide-and-conquer. A fundamental idea.

Divide-and-conquer
A fundamental idea

Philippe Dumas's home page
Divide-and-conquer | Maple
Publications | Address | Version française

Introduction
A fundamental idea
Complexity and recurrences
2-rational sequences
Asymptotic behavior
References

The divide-and-conquer strategy consists in breaking a problem into simpler subproblems of the same type, next to solve these subproblems, finally to amalgamate the obtained results into a solution to the problem. Thus it is primarily a recursive method. The algorithms of this type display two parts; the first one breaks the problem into subproblems, the second one merges the partial results into the total result.

Sorting Mergesort provides a clear example of this strategy. The data is a list of items (one also uses the word key in place of item) taken in a set endowed with a total order; the aim is to obtain a list made up of these same elements but arranged according to the order [19, pp. 305-307]. The algorithm reads as follows:

--: the list is partitioned into two half-lists;
--: each half-list is sorted;
--: the two sorted half-lists are merged.

The basic case of the algorithm is when the list contains only one key.

The implementation of the algorithm depends on the data-structure that is selected to represent the list of items; we suppose that the lists are represented by tables [19, p. 342]; one could just as easily use linked lists [34, chap. 12]. In a first version, which is an pseudo-algorithm, one merges two sorted lists into a third one. This haves the disadvantage of create a lot of lists. By a program transformation one creates the merged list in place, with the help of an auxiliary list [20, § 4.3]. In practice it is sufficient to merge two sorted lists represented by subintervals of a table, these subintervals being contiguous and of the form [i,j) and [j,k). In the Pascal procedure which follows these integers are thus the parameters, and the table is a global variable.

The implementation of the algorithm is a direct reflection of the divide-and-conquer strategy.

  procedure mergesort(var a:list; i,j:integer);
    var m:integer;
    begin
      if i+1<j then begin
        m:= (i+j) div 2;
        mergesort(a,i,m);
        mergesort(a,m,j);
        merge(a,i,m,j);
        end
    end;

For the sake of completness, let us indicate a possible version of merging.

 procedure merge(var a:list; i,j,k:integer);
   var m,n,p:integer;
       b: list;
   begin
     m:=i; n:=j; p:=i;
     while (m<j) and (n<k) do begin
       if a[m]<a[n] then begin b[p]:=a[m]; m:=m+1 end
       else begin b[p]:=a[n]; n:=n+1 end;
       p:=p+1;
     end;
     if (m<j) then for n:=m to j-1 do begin b[p]:=a[n]; p:=p+1; end
     else for m:=n to k-1 do begin b[p]:=a[m]; p:=p+1; end;
     for m:=i to k-1 do a[m]:=b[m];
   end;

Quicksort also uses the divide-and-conquer strategy. A particular element is chosen, for example the first one of the table to be sorted. The elements are partitioned according to their position compared to this distinguished key. This creates two sublists made up respectively of the elements smaller than and the elements larger than the key. The same processing is applied recursively to each sublist. Merging consists in putting the key distinguished at its right place and the two sorted sublists respectively on the left and on the right of the key.

Multiplication. The multiplication of structured objects provides another application of the divide-and-conquer strategy [20, chap. 6]. A positive integer has an expansion $(n_{\ell}\ldots n_0)_B$ with respect to the radix B, if it satisfies

$\begin{displaymath}n=n_{\ell}B^{\ell}+n_{\ell-1}B^{\ell-1}+\dotsb+n_0,\qquad 0\leq n_0,\ldots,n_{\ell}<B, \end{displaymath}$ .

This integer is seen as a table of digits. In the multiplication of two integers n and m according to Karatsuba's method the tables which represent them are broken into two parts of approximatively equal lengths. This gives the equalities

$\begin{displaymath} n=aB^k+b,\qquad m=cB^k+d\,;\end{displaymath}$ .

The following products are computed

$\begin{displaymath} x=(a+b)(c+d),\qquad y=ac,\qquad z=bd\,;\end{displaymath}$ .

Finally the product is obtained [31, p.34]

nm=y B^2k+ (x-y-z)B^k+z.

Of course products x, y and z are computed using the same strategy. Notice that the algorithm carries out three multiplications where the naive algorithm needs four. This is here the interest of the divide-and-conquer strategy lies.

The multiplication of polynomials is treated in the same way; the implementation is even simpler because there is no carry to take into account [34, chap. 36]. In the same spirit the algorithm of Strassen [27, p. 7] computes the product C=AB of two matrices A and B broken up into four blocks,

$\begin{displaymath}A=\left(\begin{array}{cc} A_{1,1}&A_{1,2}\\ A_{2,1}&A_{2,2... ...y}{cc} C_{1,1}&C_{1,2}\\ C_{2,1}&C_{2,2} \end{array}\right).\end{displaymath}$ .

The evaluation of the seven products [9, p. 739]

$\begin{displaymath} P_1=A_{1,1}(B_{1,2}-B_{2,2}),\quad P_2=(A_{1,1}+A_{1,2})B_{2,2},\end{displaymath}$

$\begin{displaymath} P_3=(A_{2,1}+A_{2,2})B_{1,1},\quad P_4=A_{2,2}(B_{2,1}-B_{1,1}),\end{displaymath}$

$\begin{displaymath} P_5=(A_{1,1}+A_{2,2})(B_{1,1}+B_{2,2}),\quad P_6=(A_{1,2}-A_{2,2})(B_{2,1}+B_{2,2}),\end{displaymath}$

$\begin{displaymath} P_7=(A_{1,1}-A_{2,1})(B_{1,1}+B_{1,2})\qquad\end{displaymath}$

yelds the matrix C,

$\begin{displaymath} C_{1,1}=-P_2+P_4+P_5+P_6,\quad C_{1,2}=P_1+P_2,\end{displaymath}$

$\begin{displaymath} C_{2,1}=P_3+P_4,\quad C_{2,2}=P_1-P_3+P_5+P_7.\end{displaymath}$

Again it is noticed that the algorithm uses seven multiplications where the naive algorithm needs eight. This leads us to expect a better behavior on large data; the phenomenon will be quantified in the last section.

Geometry. Computational geometry uses the divide-and-conquer strategy too. Let us quote for example the search of the convex hull of a finite set of points ([14, pp. 145, 158] or [32, p. 112]) or the construction of its Voronoï diagram [32, p. 213]. In the search for the convex hull of a family of n points in a plane, one proceeds as follows. First, the points are sorted according to their abscissae, and this arranges them in a list p₁, $\ldots$ , p_n. Next, the list is broken into two sublists of the same length p₁, $\ldots$ , p_k and p_k+1, $\ldots$ , p_n. The convex hulls of the two sublists are recursively built. The stopping case is the case where a list comprises at most three points. Finally the two convex hulls are merged. The difficulty lies in this last operation. To achieve it the algorithm proceeds as follows. The higher bridge and the lower bridge between the two convex hulls are built. The higher bridge is obtained in the following way. The point p_k is the rightmost point of the hull on the left-hand side, and p_k+1 is the leftmost point of the hull on the right-hand side. Two variables l and r are introduced. They are initialized respectively with the values p_k and p_k+1. The line which join l and r is denoted by L. If the point of the convex hull on the left-hand side which follows l counterclockwise is above L, then l is replaced by its successor. Likewise, if the point of the convex hull on the right-hand side which precedes r counterclockwise is above L, then r is replaced by its predecessor. Both actions are repeated as long as possible. At the end the line L provides the higher bridge. The lower bridge is obtained in the same way.

Previous page:	Introduction
Next page:	Complexity and recurrences