View more random threads:
- PHY101 Physics Assignment No. 01 Fall Semester 2013 Due...
- CS301 Assignment # 4
- CS201-Introduction to Programming Assignment No.2 Due Date...
- Mth202 assigment 1 fall 2010
- cs610 5th assignment solution for sale.......!!!!!!!
- CS302 Digital Logic Design Assignment # 2 Spring 2010
- CS401 - Computer Architecture and Assembly Language...
- Cost & Management Accounting (Mgt 402) Assignment No. 1...
- MGT411 Money and Banking Assignments NO.02 Last Date 30th...
- STA301- Statistics and Probability GDB No.1 Solution Fall...
CS502 Fundamentals of Algorithms Assignment No.1 Solution Spring Semester 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.
Uploading instructions:
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).
Save your assignment with your ID (e.g. bc020200786.doc).
No assignment will be accepted through email.
Rules for Marking:
It should be clear that your assignment will not get any credit if:
Sponsored Links
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.
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 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
There are currently 1 users browsing this thread. (0 members and 1 guests)