Divide-and-Conquer Suppose that a computer does not know how to compute the valu

Question

Divide-and-Conquer Suppose that a computer does not know how to compute the value Cn2 directly if n > 2, but the computer can return

C22 = 1 in constant time. Also, the computer takes only constant time for scalar arithmetic operations.

We can use divide and Conquer technique to compute Cn2 as follows.

Cn2 ={1 if n = 2 }
{ 2C n/2 2 + (n/2)2 if n = 2k , where k > 1 is a positive integer }

Please write down the three steps Divide, Conquer and Combine to describe how the computer calculates Cn2

Please write down the running time recurrence if Cn2 is computed using the above approach.

Explanation / Answer

Please write down the three steps Divide, Conquer and Combine to describe how the computer calculates Cn2

The answer to this question is central to the concept of Divide-&-Conquer algorithm and is a key factor in gauging their efficiency.

Consider the following: We have an algorithm, alpha say, which is known to solve all problem instances of size n in at most c n^2 steps (where c is some constant). We then discover an algorithm, beta say, which solves the same problem by:

Suppose our original algorithm, alpha, is used to carry out the `solves these sub-instances' step 2. Let

T(alpha)( n ) = Running time of alpha

T(beta)( n ) = Running time of beta

Then,

T(alpha)( n ) = c n^2 (by definition of alpha)

But

So if dn < (cn^2)/4 (i.e. d < cn/4) then beta is faster than alpha

In particular for all large enough n, (n > 4d/c = Constant), beta is faster than alpha.

This realisation of beta improves upon alpha by just a constant factor. But if the problem size, n, is large enough then

which suggests that using beta instead of alpha for the `solves these' stage repeatedly until the sub-sub-sub..sub-instances are of size n0 < = (4d/c) will yield a still faster algorithm.

So consider the following new algorithm for instances of size n

Let T(gamma)(n) denote the running time of this algorithm.

We shall show how relations of this form can be estimated later in the course. With these methods it can be shown that

T(gamma)( n ) = O( n^{log3} ) (=O(n^{1.59..})

This is an asymptotic improvement upon algorithms alpha and beta.

The improvement that results from applying algorithm gamma is due to the fact that it maximises the savings achieved beta.

The (relatively) inefficient method alpha is applied only to "small" problem sizes.

The precise form of a divide-and-conquer algorithm is characterised by:

In (II) it is more usual to consider the ratio of initial problem size to sub-instance size. In our example this was 2. The threshold in (I) is sometimes called the (recursive) base value. In summary, the generic form of a divide-and-conquer algorithm is:

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects