SUMMER TRAINING Free Tutorials  Go To Your University  Placement Preparation 
Project Based Best Summer Training Courses in Jaipur
Join our Telegram Channel To take free Online Courses
0 like 0 dislike
79 views
in Examples, Exercises and Projects by (562 points)
edited by

In this article,you will know

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

1 Answer

0 like 0 dislike
by (562 points)
selected by
 
Best answer

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)

    


Our Mentors(For AI-ML)


Sharda Godara Chaudhary

Mrs. Sharda Godara Chaudhary

An alumna of MNIT-Jaipur and ACCENTURE, Pune

NISHA (IIT BHU)

Ms. Nisha

An alumna of IIT-BHU

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...