cs502 assignment no 1 on 08 April Spring 2011 Idea solution and discussion

[Vuhelper]

Fundamentals of Algorithms
CS502-Fall 2010

SHORT ASSIGNMENT
Deadline

Your assignment must be uploaded/submitted at or before 8th November 2010.
Uploading instructions

Please view the assignment submission process document provided to you by the Virtual University to upload the assignment.
Rules for Marking

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

oThe assignment is submitted after due date.
oThe submitted assignment does not compile or run.
oThe assignment is copied.
Objectives

This assignment will help you to understand the concepts of Asymptotic Growth, making analysis of pseudo code, recurrence relation development, asymptotic function understanding and iterative solutions for recurrences.
Guidelines

RULES FOR CALCULATING TIME COMPLEXITY AND BIG-OH

Rule 00
Normally these formulas are very handy:

If then
Also,



Rule 0
The condition that stops a loop executes ONE MORE time than the loop itself (the last time is when it is evaluated false)

Rule 1
for (i=0;i<n;i=i+k) Anything inside the loop will run approximately n/k times

Rule 2
for (i=n;i>0;i=i-k) Anything inside the loop will run approximately n/k times

Rule 3
for (i=1;i<n;i=i*k) Anything inside the loop will run approximately logkn times

Rule 4
for(i=1;i<=n;++i)
for (j=1;j<=i;++j)
The above nested loop approximately runs ½ n(n+1) times.
The variable j depends upon the value of i

Rule 5
for(i=1;i<=n;i=i*2)
for (j=1;j<=i;++j)
The statements in the above nested loop approximately run 2n-1 times.
The variable j depends upon the value of i


Rule 6
If the loop variables are independent then the total times a statement inside a nested loop is executed is equal to the product of the times the individual loops run
e.g. for (i=0;i<n;++i)
for (j=0;j<m;++j)
A statement inside the above nested loop will run n*m times



Estimated Time 2.5 hour
For Q1 maximum time is 1.25 hour and for Q2 maximum time is 1.25 hour. It all depends upon your sheer concentration.

Question 1 (10)
Find the running time complexity of the following piece of code and show your working step by step.
1. y=0;
2. x=0;
3. for (i=n; i>0;i=i-1)
4. { y=y+1;}

5. for (i=1;i<=n;i=i*3)
6. { for (j=1;j<=3n;++j)
7. {
a. for(k=0;k<n; k=k+5)
i. {
ii. x=x+5;
iii. }
8. }
9. }



Solution Q1
Code Line Time taken Comments
1 y=0 1(Constant)
2 x=0 1
3 for (i=n; i>0;i=i-1)
n+1 Outer independent loop;”1” time more then “n” for condition checking at end.
4 y=y+1 n As entrance in loop is “n” time
5 for(i=1;i<=n;i=i*3)
log3n+1 As step size is multiplied by three that’s why log to the base 3 (rule 3)
6 for(j=1;j<=3n;++j)
3n(log3n)+1 As for each iteration of outer loop this loop will execute for 3n times
7 a for(k=0;k<n;k=k+5)
(n/5)3n(log3n)+1=(3n2 log3n )/5+1 As this is the inner most loop and for each above two loops it will execute n/5 times (rule 1)
7 a i x=x+5;
(n/5)3n(log3n)=(3n2 log3n) /5 This statement is under the second inner loop.

From above explanation over all time will be summed up to take final one.
T(n)=1+1+n+1+n+log3n+1+3n(log3n)+1+(3n2 log3n) /5+1+
(3n2 log3n) /5
=6+2n+ log3n+3n(log3n)+ (6n2 log3n) /5 as the leading term is (6n2 log3n )/5 so we can asymptotically bound the code run time by this.














Question 2 (10)
Solve the following recurrence relation using iterative method and make proper assumptions for final solution and give answer at end in asymptotic form.




Assume n to be a power of 5, i.e., n = 5k and k = log5n