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

# www.vustudents.ning.com

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + 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

# Assignment No. 01 Semester: Spring 2013 CS502-Fundamentals of Algorithms, Total Marks: 20 Due Date: 29/04/2013

 Assignment No. 01 Semester: Spring 2013

CS502-Fundamentals 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.

Please view the Assignment Submission Process document provided to you by the Virtual University for uploading assignments.

• Your assignment must be in .doc format. (Any other formats like scan images, PDF, Zip, rar, bmp etc. will not be accepted).
• No assignment will be accepted through email.

Rules for Marking:

It should be clear that your assignment will not get any credit if:

• The assignment is submitted after due date.
• The submitted assignment does not open or file is corrupted.
• Your assignment is copied from internet, handouts or from any other student

(Strict disciplinary action will be taken in this case).

Question: 1                                       marks : 10

Analyze the following pseudo code containing nested loops by computing its worst-case running time complexity. Perform all the steps by writing out the loops as summations and then solve the summations.

1. for  i = 1    to   log n
2. {          set   j = 1 ;       // ignore its constant time in analysis
3.              while ( j <= i )
4.              {         for  k = 1    to  j
5.                          {         k=k+1;
6.                          }
7.             j  = j * 2 ;         // ignore its constant time in analysis
8.            }
9. }

[Note: Consider log as base 2 log and computing model  as RAM (Random Access Machine) like one used in lectures ]

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]

NOTE: Submit “.doc” file only. Every student should provide his/her own work, exact copying of the assignment (or some portion of the assignment) from the internet or other students will lead to copy case and zero marks will be awarded. Different softwares will be used to check plagiarism in assignments. Do not put any query on MDB about this assignment, if you have any query then  email at CS502@vu.edu.pk

+ 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?

Views: 8615

.

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

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

Attachments:

### Replies to This Discussion

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 worst-caserunning 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 ]

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 inside-out. 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.

F(n) = 2n^3 + 3n^2-2n
Lower Bound:
G(n^3)
For this we show that f(n) >=c1n^3 and n>=n0
F(n)= 2n^3 + 3n^2 - 2n >=  2n^3 -2n = n^3 +( n^3 -2n) >= n^3
n^3 is compare with c1n^3 so
c1 = 1
We implicitly assumed that 3n^2 >= 0 and n^3 - 2n >=0  These are not true for all n . If n >=2 then it is true for both. We chek this by putting values in 3n^2 >= 0 and n^3 - 2n >=0  .
Now n>=under root(2) so n0 >= 2    So f(n) >= C1n^3 for all n>=n0
Upper Bound:
F(n)= 2n^3 + 3n^2 - 2n <= 2n^3 + 3n^2 <= 2n^3 + 3n^3 = 5n^3
By compare 5n^3 with c2n^3 So c2 = 5
We implicitly made the assumption that 3n^2 <= 3n^3
It is true for all n >= 1  So n0 >= 1
From lower bound n0 >= under root(2)
Upper bound n0 >= 1
By combining both n0 >= underroot(2) , c1 = 1 , c2 = 5 so we get  asymptoticequivalence  n^3 <=  2n^3 + 3n^2 - 2n <= 5n^3 for all n >= under root(3)

[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.

any authentic solution????

authentic means???????    Q2 part a ... answer ???

Mra Question 2 Part a reh gya    .