Divide-and-conquer A fundamental

posted on 23 Jun 2008 10:47 by vicsviper in Algorithm

On sunday i have a class at Thammasart University about Algorithm. The lesson told about how to solve a problemand sorting data by division,the 1 easy way to sorting data in computer system.

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. 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, one could just as easily use linked lists. 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. 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.

Multiplication. The multiplication of structured objects provides another application of the divide-and-conquer strategy. 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

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 . In the same spirit the algorithm of Strassen 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

$\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 or the construction of its Voronoï diagram . 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.