Lebanese International University
Department of Computer Science
CSCI 510 – Design and Analysis of Algorithms
Assignment 1
Question 1:
a. Consider the following function that computes the sum of the elements of an array
iteratively:
int arraySum (int [] a, int n) {
int sum = 0;
n = [Link]();
for (int i = 1; i < n; i++)
sum += a[i];
return sum;
}
1) What is the complexity of this function?
O(N)
2) Write a recursive function that performs the same task. Extract the recurrence relation
and solve it to conclude the time complexity of this function.
int [] a;
int recsum ( a, int n){
n =[Link]()
if (count <=0)
return 0;
else
return recsum(a,n-1) + a(n-1);
}
Page 1 of 10
b. Prove the following function is O(n 4 ) by finding C0 and N0: T(n) = 2n 4 −
20n 3 − 200n 2 + 500n + 5000
T(n)= 2n 4 − 20n 3 − 200n 2 + 500n + 5000 and F(n)= n 4
< = 2n 4 − 20n 3 − 200n 2 + 500n + 5000 for n>=1 (n0=1)
< = 2n 4 − 20 n 4 − 200 n 4 + 500 n 4 + 5000 n 4
<= 5,282 n 4
<= c0F(n)
T(n)<=O(F(n)) when c0=5282 and n0=1
c. Solve the following recurrence relation: T(N)=4*T(N/2)+N2 and T(1) = 1
T(N) = 4*T(N/2)+N2 and T(1) = 1
= 4T(N/2)+N2
= 4(4T(N/4) +(N/2) 2 ) + N2
= 16T(N/4) + 4(N/2) 2 + N2
= 42 T(N/4) + 4(N/2) 2 + N2
= 4i T(N/2i ) + 2i (n/i) i +Ni
Until i=2/N
N*2-i
... until (
N/2i )= 1
log(
N/2i )= log(1)
2
log(N)/log( i ) = log(1)
log(N) /ilog(2)= log(1)
N/2i=1
n=2i
Page 2 of 10
i=n/2
Question 2:
a- Extract the recurrence relation of the following method and
solve it
public static void Test ( int N){
if(N>1)
{ Test(N/3);
[Link](N);
Test(N/3);
[Link](N);
Test(N/3);
}
T(N)=T(3(N/3))+1
b- Extract the recurrence relation of the following method and
solve it
T(n)=T(n/2)2 + T(n/2)2 +1
Question 3:
Page 3 of 10
Give the time complexity using Big-Oh notation. Assume an input of size n
1.
for (int i = n; i > 0 ; i-- ) {
for ( int j = 1; j < n; j ++ )
[Link](j, i);
for( int k = n; k > 1; k = k - 2)
[Link](k, i);
}
N(N+N)= N(2N) =2N^2
so the time complexity is O(n2 )
2.
sum = 0 ; for(i=1; i<=3*n;
i++)
sum = sum + 1;
O(n)
3.
sum = 0 ;
for(i=1; i<=n*n+1; i++) sum =
sum + 1 ;
O(n2)
4.
sum = 0 : for(i=-1; i<=n+2; i++) sum = sum + n ;
O(n)
5.
Page 4 of 10
sum = 0 ; for(i=1;
i<=n; i++)
for(j=1; j<=n; j*=2)
sum = sum + 1 ;
n*log2n
O(nlogn)
6.
for (int k = 1; k < n; k++)
{ j = n; while (j >0)
{ [Link](j);
j = j / 2;
}
}
n*log2n
O(nlogn)
7.
for (int i = 1; i <= 5; i++)
for (int j = 1; j <= n; j ++)
for (int k = 1; k <= 3; k++)
[Link](i, j*i, j*k);
O(n)
Question 5:
Page 5 of 10
1. Consider the following method:
public static void mystery (int v)
{ if(v<0)
mystery(v+2);
[Link](v + "-"); }
What is printed by the call mystery (-5). Show your tracing?
mystery (-5)
if(v<0) // true
mystery(v+2);
[Link]( -5 + "-");
mystery(-3)
if(v<0) // true
mystery(v+2)
[Link](-3 + "-");
mystery (-1) if(v<0) // true
mystery(v+2)
[Link](-1 + "-");
mystery (1) if(v<0) // false
[Link](1 + "-");
output :
1--1--3--5-
Page 6 of 10
What is the recurrence relation (CN) of the above mystery method?
T(v)=4T(v+2) +1
Question 5:
Consider the following method:
public String method(String first, String second)
{ if(first ==null || [Link](“”))
return second;
else
if (second == null || [Link](“”)) return
first;
else
if([Link](0) < [Link](0))
return [Link](0) + method( [Link](1, [Link]()), second);
else
return [Link](0) + method(first, [Link](1,
[Link]())); }
What does the above method do?
It is sorting the characters of the given strings
Question 6: After you delete the nodes 11, 7 and 5 (preserve the order), show the
final BST.
Page 7 of 10
Page 8 of 10
Question 7:
Prove that f(x) = x3 + 3x2 – 45 is big theta of (x3)
Assignment Guidelines:
• This assignment is handed on Tuesday, November 17, and is due by uploading it on
Classroom on Monday, November 23 (before midnight)
• Every one-day late will lead to a 20% deduction
• A “PDF” document containing the questions and their corresponding “CLEAR” answers is
highly recommended.
• I trust that your high ethical standards will prevent you from copying the answers from your
colleagues or somewhere else.
Page 6 of 6