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

Question

In this article,you will know

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

Answer 1

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 P₁,P₂,.......P_k.
• 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 n₁,n₂,....n_k  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 P₁,P_x,....P_k.

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

   ₁),DNC(P₂),.....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=2^k and T(2^k)=t_k 

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

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

Replacing k by k-1 we get,

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

Multiply eq(ii) by 2 ,we get

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

Substract (iii) from (i) ,we get

⇒t_k-2t_k-1=4t_k-1-8t_k-2  

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

Let,t_k=x^k  

⇒x^k-6x^k-1+8x^k-2=0

      or

⇒x²-6x+8=0

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

⇒t_k=c₁2^k+c₂4^k

Putting back n, we get

⇒T(n)=c₁n+c₂n²  

Therefore,T(n)£O(n²)

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

Solution:

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

Since n>1 and is power of 2 ,

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

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

And replacing k by k-1 ,we get

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

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

⇒t_k-4t_k-1=4t_k-1-16t_k-2  

         or

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

Putting t_k=x^k,we get

⇒x^k-8x^k-1+16x^k-2=0 

⇒   x²-8x+16=0

⇒(x-4)²₌₀

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

    

---