We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

Looking For Something at vustudents.ning.com? Click Here to Search

www.bit.ly/vucodes

+ Link For Assignments, GDBs & Online Quizzes Solution

www.bit.ly/papersvu

+ Link For Past Papers, Solved MCQs, Short Notes & More

CS502 Assignment No. 02 Solution & Discussion Due Date: Dec 07, 2015

CS502 - Fundamentals of Algorithms Assignment No. 02 Solution Fall 2015 Due Date Dec 07, 2015

Assignment No. 02
Semester: Fall 2015

CS502: Fundamentals of Algorithms

Due Date:07/12/2015

Instructions

Please read the following instructions carefully before submitting assignment:

 

It should be clear that your assignment will not get any credit (zero marks) if:

  • The assignment is submitted after due date.
  • The submitted assignment is other than .doc file.
  • The submitted assignment does NOT open or file is corrupted.
  • The assignment is copied (from other student or ditto copy from any other source).

 

Objective

 

The objective of this assignment is to enable students:

 

  • Write and solve recurrence relations of recursive algorithms using iteration method
  • Design algorithm using Divide and conquer approach

 

Submission

 

You are required to submit your solution through LMS as MS Word document.

 

For any query about the assignment, contact at CS502@vu.edu.pk

                                                             GOOD LUCK

 

Question 1:

 

Consider the following recursive algorithm for computing the sum of the first n squares:

Sum(n) = 12 + 22 + . . . + n2.

 

Algorithm: SUM(n)

if n = 1 return 1

else return SUM(n − 1) + n ∗ n

 

Write recurrence relation for above algorithm and solve it using Iteration Method.

 

Question 2:

 

In Divide and conquer strategy, three main steps are performed:

 

  1. 1.      Divide: Divides the problem into a small number of pieces
  2. 2.      Conquer: Solves each piece by applying divide and conquer to it recursively
  3. 3.      Combine: Combines/merges the pieces together into a global solution.

 

Write an algorithm to find minimum number from a given array of size ‘n’ using divide and conquer approach.

 

 

Lectures Covered:  This assignment covers first 15 Lectures.

Deadline:             Your assignment must be uploaded/submitted at or before 07 Dec, 2015. 

+ Click Here To Join also Our facebook study Group.

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?


See Your Saved Posts Timeline

Views: 17803

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

+ Click Here to Search (Looking For something at vustudents.ning.com?)

Replies to This Discussion

true solution

Part1

T(n)=T(n-1)+n*n     

as we know that T(n-1)=T(n-2)+n*n

 so we put this value

T(n)=T(n-2)+n*n+n*n =T(n-2)+2(n*n)

T(n)= T(n-2)+2(n*n)          T(n-2)=T(n-3)+n*n so we put this value

T(n)= T(n-3)+2(n*n)+n*n=T(n-3)+3(n*n)     

T(n-3)+3(n*n)      T(n-3)=T(n-4)+n*n so we put this value

T(n)=T(n-4)+3(n*n)+n*n=T(n-4)+4(n*n)

..........

T(n)= T(n-k)+k(n*n)

If we set n=k

Then

T(n)= T(n-n)+n(n*n)=n^3

Part2:

SELECT(Array A,int p ,intr,int k=1)

if(p=r)

then return A[p]

else xßCHOOSE_PIVOT(A,p,r)

q ß PARTITION (A,p,r,x)

rankxß q-p+1

ifk=rankx

then return x

ifk<rankx

then return SELECT(A, p ,q-1, k)

Tariq bhai part 2 mai kia kia hai?

kr de copy paste phir

Very gud dude main b yehi krny lga bs

Tariq bhai kia cnfrm hai ye solution?

Part1

T(n)=T(n-1)+n*n             as we know that T(n-1)=T(n-2)+n*n so we put this value

T(n)=T(n-2)+n*n+n*n =T(n-2)+2(n*n)

T(n)= T(n-2)+2(n*n)                                       T(n-2)=T(n-3)+n*n so we put this value

T(n)= T(n-3)+2(n*n)+n*n= T(n-3)+3(n*n)     

 T(n-3)+3(n*n)                                                 T(n-3)=T(n-4)+n*n so we put this value

T(n)=T(n-4)+3(n*n)+n*n=T(n-4)+4(n*n)

..........

T(n)= T(n-k)+k(n*n)

If we set n=k

Then

T(n)= T(n-n)+n(n*n)=n^3

 

Part2:

SELECT(Array A,int p ,int r,int k=1)

if(p=r)

then return A[p]

else x  ßCHOOSE_PIVOT(A,p,r)

q ß PARTITION (A,p,r,x)

rankx  ß  q-p+1

if k= rankx

then return x

if k< rankx

then return SELECT(A, p ,q-1, k)

tarik bi help us is it correct and complete sol.

plzzz help us bro.

Tariq bhi mujhay sirf ina bta day k yeh theek soution hn na,..??
ap nay pehlay bhi aik solution bheja tha mn confirm nhi ..

RSS

Latest Activity

© 2019   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service