CS502-Fundamentals of Algorithms Assignment No. 01 Spring 2013

Admin

Assignment No. 01
Semester: Spring 2013

CS502-Fundamentals of Algorithms

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:
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:

Part (a)

What is the Asymptotic equivalence ( ) of the below function f(n)?

f(n) = 2n³ + 3n² – 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 n⁰]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