We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>
+ Link For Assignments, GDBs & Online Quizzes Solution 
+ Link For Past Papers, Solved MCQs, Short Notes & More 
Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion
How to Add New Discussion in Study Group ? Step By Step Guide Click Here.
Assignment No. 01 
CS502Fundamentals of Algorithms
Total Marks: 20 Due Date: 29/04/2013 
Lectures Covered: 1 to 6
Objective 
To analyze pseudo code and solve using summations; understand and prove asymptotic notations.
Uploading instructions: Please view the Assignment Submission Process document provided to you by the Virtual University for uploading assignments.
Rules for Marking: It should be clear that your assignment will not get any credit if:
(Strict disciplinary action will be taken in this case). Question: 1 marks : 10

Tags:
+ How to Follow the New Added Discussions at Your Mail Address?
+ How to Join Subject Study Groups & Get Helping Material? + How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators? + VU Students Reserves The Right to Delete Your Profile, If?.
+ 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)
Question: 1
For inner FOR loop
I(j)=Σ1=j
For middle WHILE loop
M(i)= ΣI(j)
=Σj
=i(i+1)/2
For outer FOR loop
T(n)= ΣM(i)
Σ i(i+1)/2
=1/2[Σi^2 + Σi] summation apply
Σi^2 = [2(logn)^3 + 3(logn)^2 + logn]/6
Σi = logn(logn + 1)/2
is it correct?
koi to authentic solution upload kar do dosto :s
Question: 1 marks : 10
Analyze the following pseudo code containing nested loops by computing its worstcaserunning time complexity. Perform all the steps by writing out the loops as summations and then solve the summations.
for i = 1 to log n
{ set j = 1 ; // ignore its constant time in analysis
while ( j <= i )
{ for k = 1 to j
{ k=k+1;
}
j = j * 2 ; // ignore its constant time in analysis
}
}
[Note: Consider log as base 2 log and computing model as RAM (Random AccessMachine) like one used in lectures ]
Answer:
we analyze the running time of an algorithm that has many complex nested loops? The
answer is that we write out the loops as summations, and then try to solve the summations. Let I(),
M(), T() be the running times for (one full execution of) the inner loop, middle loop, and the entire
program. To convert the loops into summations, we work from the insideout. Let’s consider one pass
through the innermost loop. The number of passes through the loop depends on j. It is executed for
k = j; j−1; j−2;:::;0, and the time spent inside the loop is a constant, so the total time is just j+ 1.
We could attempt to arrive at this more formally by expressing this as a summation:
I(j) =Xj
k=0
1 = j + 1
Why the “1”? Because the stuff inside this loop takes constant time to execute. Why did we count
up from 0 to j (and not down as the loop does?) The reason is that the mathematical notation for
summations always goes from low index to high, and since addition is commutative it does not matter
in which order we do the addition.
Question: 2 Marks: 10
Part (a)
What is the Asymptotic equivalence ( ) of the below function f(n)?
f(n) = 2n3 + 3n2 – 2n
Part (b)
Prove the Asymptotic equivalent of function in Part (a) by its lower and upper bounds.
[Note: You do not need to draw the graph, only show lower and upper bounds with c1,c2 and n0]
+ Fatima gud keep it up
Note for All Members: You don’t need to go any other site for this assignment/GDB/Online Quiz solution, Because All discussed data of our members in this discussion are going from here to other sites. You can judge this at other sites yourself. So don’t waste your precious time with different links.
authentic means???????
Q2 part a ... answer ???
Mra Question 2 Part a reh gya
© 2020 Created by + M.Tariq Malik. Powered by
Promote Us  Report an Issue  Privacy Policy  Terms of Service
VU Students reserves the right to delete profile, which does not show any Activity at site nor has not activity more than 01 month.
We are usergenerated contents site. All product, videos, pictures & others contents on vustudents.ning.com 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 or Contact us at contact 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