# What do you mean by divide and conquer strategy in Data structure and algorithm?

0 like 0 dislike
951 views

edited

1. Divide and conquer strategy
2. Its problems with solutions

0 like 0 dislike
by (562 points)
selected

# Divide and Conquer  Strategy

• A control abstraction indicates the way in which an actual program perform its task based on divide and conquer strategy.
• It clearly shows the flow of control,but the primary operations are specified by other procedures.
• The control abstraction is written either recursively or iteratively.
• However ,the basic  functionality of either method is same.
• Consider the algorithm,divide and conquer given below.
• The algorithm is initially involved as DNC(P) ,where P is the problem to be solved.
• P is a boolean valued function used for determining whether the input size is small enough to compute the answer without any splitting.If this is so,the function S is involved ,otherwise the problem P is broken down into smaller sub problems such as P1,P2,.......Pk.
• These sub problems are solved by recursive applications of divide and conquer .Combine is a function that can find the solution to P by using the solutions to the K subproblems.
• If the size of P is n and the size of the K sub problems are n1,n2,....nk  respectively.
• Then ,the computing time of divide and conquer is described by the recurrence relation.

## Algorithm:

### Control Abstraction for Divide and Conquer

Algorithm DNC(P)

1. {

2. if P then return S(P)

3. else

4. {

5. divide P into smaller instances P1,Px,....Pk.

6. Apply DNC to each of these sub problems. return combine(DNC(P

1),DNC(P2),.....DNC(AC)}

7. }

P)Show the recurrence T(n)=4T(n/2)+n ,where n≥1 and is a power of 2.

Solution:

Let ,n=2k and T(2k)=tk

⇒T(2k)=4T(2k-1)+2k

⇒tk=4tk-1+2k            .........     (i)

Replacing k by k-1 we get,

⇒tk-1=4tk-2+2k-1       ................(ii)

Multiply eq(ii) by 2 ,we get

⇒2tk-1=8tk-2+2k        ................(iii)

Substract (iii) from (i) ,we get

⇒tk-2tk-1=4tk-1-8tk-2

⇒tk-6tk-1+8tk-2=0

Let,tk=xk

⇒xk-6xk-1+8xk-2=0

or

⇒x2-6x+8=0

⇒(x-2)(x-4)=0

⇒tk=c12k+c24k

Putting back n, we get

⇒T(n)=c1n+c2n2

Therefore,T(n)£O(n2)

P:2)Solve the following recurrence relation   T(n)=4T(n/2)+n2 ,where n>1 and is equal to power of 2.

Solution:

Recurrence relation,T(n)=4T(n/2)+n2

Since n>1 and is power of 2 ,

put n=2k and T(2k)=tk to get,

⇒tk=4tk-1+22k          .......   (i)

And replacing k by k-1 ,we get

⇒tk-1=4tk-2+22(k-1)     ........(ii)

mulitiply 4*(ii) and subtract equation (i) from it,we get

⇒tk-4tk-1=4tk-1-16tk-2

or

⇒  tk-8tk-1+16tk-2=0

Putting tk=xk,we get

⇒xk-8xk-1+16xk-2=0

⇒   x2-8x+16=0

⇒(x-4)2=0

Therefore,T(n)£O(n2 logn)