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

[Xpert]

Fundamentals of Algorithms
CS502-Spring 2011
ASSIGNMENT1
Deadline
Your assignment must be uploaded/submitted at or before 18th April 2011.
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 x y = z then y z x = log
Also,
( )
2 1
1
n
n
i
i a a n a + = Σ=
( 1)
1 2
+ = Σ=
i n n
n
i r
r r
m m
k
k
−
−
=
+
= Σ
1
1 1
0
( for n 1)
6
( 1)(2 1)
1
2 >=
+ +
= Σ=
i n n n
n
i
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
Other Guidelines
While loop related information
Complexity of “while” loop depend upon the initial entrance condition if it remains
true for “n” iterations it will be “n+1” ;Note here “1” will be added for the last time
check of the condition .Here this will be clear to you if the some logical conditions
are checked other then counters then all complexity will be based on scenario of
the problem and nature of the logical condition.
Function Growth rate concept
If some function f1(x)>f2(x) for positive values of x then the function f1(x) is said to have
greater growth rate then f2(x). For example f1(x)=x5 and f2(x)= x6 it is obvious that f1(x)
has greater growth rate ( 26 > 25).This concept relate to complexity of algorithm ,an
algorithm having greater growth rate function means the algorithm has greater
complexity here f2(x) is more complex then f1(x).
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.
y=0;
x=0;
for(i=m; i>-2; i=i-2)
{ x++; }
for (i=n; i>0;i=i-1)
{ y=y+1;}
for (i=1;i<=n;i=i*5)
{ for (j=1;j<=5n;++j)
{
for(k=0;k<n; k=k+4)
{
x=x+5;
}
}
}
While(i<=z)
{
i++;
}
Question 2 (10)
Arrange the following in the Most to Least complexity order. Here “n “is the input size
for the some complexity function and k< j and j & k are numbers greater than 2.Every
function is separated by “comma” and note these are 20 functions to arrange.
2
2 4 8
5 6
n, n / 2, n j/2, nlgn, nn, 1,100, 2n, lgn, n!,(n! ) / ,
/ ,n! log / , / log ,10000,n / , (log ) ,
n / , (log ) ,1000
k n n n
n n n n n n n nn n n
n n n n

[moon13]

please upload the solution of this assignment immadiatly

[Xpert]

oright just wait

[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

[moon13]

please check the solution file it is not releted to the orignal assignment

[sana.pari]

tu app check ker len na khud hi

[shifty]

Wrong solution

[Xpert]

If wrong then post the correct one.

[shifty]

I have solved the question no.2

[Xpert]

where it is?