11-13-2014, 09:56 PM
CS502-Fundamentals of Algorithms Assignment No. 01 (Graded)Due Date: 20-11-2-14
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;i0;i=i-k) Anything inside the loop will run approximately n/k times
Rule 3
for (i=1;if2(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 f2(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 3 hours
For both questions to understand; maximum time is 1.50 hours and for solution
maximum time is 1.50 hours. It all depends upon your sheer and devoted
concentration.
Special notes:
To solve the assignment you should have grip on the delivered
lessons and also consult above guidelines to perceive completely.
Your own effort is appreciated and you will rewarded…
Note:Those stuents who will Copy and pate assignment from
internet or from any other source as its will be rewarded as F. in
this course …
Question 1 (10)
Find the running time complexity of the following piece of code and show
your working step by step.
yz =0;
xw=0;
for(i=m; i>-6; i=i-6)
{ xw++; }
for (i=n; i>-2015;i=i-5)
{ yz=yz+1;}
for (i=1;i<=n;i=i*5) { for (j=1;j<=5n;j*12 { for(k=n;k<-5; k=k-4) { x=x+12 } } } Print x; While(k<=z) { k=k*2 ( for(m=k; m<=-100000; m=m-1 ) } Print k; Question 2 (10) Arrange the following in the Most to Least complexity order. Here “n “is processing steps for some complexity functions and j< k and j & k are numbers greater than 2. Every function is separated by “comma”. Note: These functions must be arranged on generic basis. Further there are 20 functions to arrange and each line has five functions. 2 3 2 2 12 2 2 4 2 2 3 5 5 8 7 ) /1000 n-1000og j/2 n/1000000, n , n , 1000 og n , n , log n 1000n 1 1000000000000, , 2 , og ( , 100000n!, 10000 1000 (n! og n), / ,n! og n / ,10000 og ( og ),10000, 1 1000n / , ( og n) , n , ( o 2150 n k L nL n L nL n n nL n L L n j n n L n n L 9 5 8 2 og j/2 g n) ,100000 og ,2199nn L n L Think Beyond The Boundaries. First Food for Thought….