+ Link For Assignments, GDBs & Online Quizzes Solution |
+ Link For Past Papers, Solved MCQs, Short Notes & More |
CS502 Assignment No. 02 Solution & Discussion Due Date: Dec 07, 2015
Assignment No. 02 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:
Objective
The objective of this assignment is to enable students:
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:
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. |
Tags:
+ 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?) + Click Here To Join (Our facebook study Group)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)
kr de copy paste phir
Very gud dude main b yehi krny lga bs
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 ..
© 2021 Created by + M.Tariq Malik.
Powered by
Promote Us | Report an Issue | Privacy Policy | Terms of Service
We are user-generated contents site. All product, videos, pictures & others contents on site don't seem to be beneath our Copyrights & belong to their respected owners & freely available on public domains. We believe in Our Policy & do according to them. If Any content is offensive in your Copyrights then please email at m.tariqmalik@gmail.com Page with copyright detail & We will happy to remove it immediately.
Management: Admins ::: Moderators
Awards Badges List | Moderators Group
All Members | Featured Members | Top Reputation Members | Angels Members | Intellectual Members | Criteria for Selection
Become a Team Member | Safety Guidelines for New | Site FAQ & Rules | Safety Matters | Online Safety | Rules For Blog Post