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:
true solution
Part1
T(n)=T(n1)+n*n
as we know that T(n1)=T(n2)+n*n
so we put this value
T(n)=T(n2)+n*n+n*n =T(n2)+2(n*n)
T(n)= T(n2)+2(n*n) T(n2)=T(n3)+n*n so we put this value
T(n)= T(n3)+2(n*n)+n*n=T(n3)+3(n*n)
T(n3)+3(n*n) T(n3)=T(n4)+n*n so we put this value
T(n)=T(n4)+3(n*n)+n*n=T(n4)+4(n*n)
..........
T(n)= T(nk)+k(n*n)
If we set n=k
Then
T(n)= T(nn)+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ß qp+1
ifk=rankx
then return x
ifk<rankx
then return SELECT(A, p ,q1, k)
kr de copy paste phir
Very gud dude main b yehi krny lga bs
Part1
T(n)=T(n1)+n*n as we know that T(n1)=T(n2)+n*n so we put this value
T(n)=T(n2)+n*n+n*n =T(n2)+2(n*n)
T(n)= T(n2)+2(n*n) T(n2)=T(n3)+n*n so we put this value
T(n)= T(n3)+2(n*n)+n*n= T(n3)+3(n*n)
T(n3)+3(n*n) T(n3)=T(n4)+n*n so we put this value
T(n)=T(n4)+3(n*n)+n*n=T(n4)+4(n*n)
..........
T(n)= T(nk)+k(n*n)
If we set n=k
Then
T(n)= T(nn)+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 ß qp+1
if k= rankx
then return x
if k< rankx
then return SELECT(A, p ,q1, 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 ..
How to Get This Badge at Your Profile DP

Management: Admins ::: Moderators
© 2021 Created by + M.Tariq Malik. Powered by
Promote Us  Report an Issue  Privacy Policy  Terms of Service
We are usergenerated contents & noncommercial 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. All Contents on site are for personal & noncommercial use.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 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