CS502 Fundamentals of Algorithms Assignment No.1 Solution Spring Semester 2013

[Vuhelper]

View more random threads:

• MCM304 Mass Media in Pakistan Assignment No.1 Solution...
• CS 101 Introduction to Computing Assignment 4 Deadline 23...
• ENG301 Assignment 4 Deadline 28 July 2010
• FIN611 First Assignment idea solution October, fall 2012
• CS504 Software Engineering - I Assignments No.04 (Non...
• Managerial Economics - Eco404 Assignment No.1 Solution Fall...
• Acc311 Assignment # 1 Solution Fall October 2010
• ISL201 Assignment No. 01 Spring 2010 May 6
• Check Online MTH401 Assignment No: 1 Fall 2014 Solution and...
• Advertising & Promotion (MKT621) Assignment No. 01 ...

Sponsored Links

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:



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