Scribd
Upload
53 views

Mohammad Mahdi Swaidan

This document contains an assignment for a computer science course on algorithms. It includes 7 questions covering topics like analyzing time complexities of functions, solving recurrence relations, and analyzing algorithms. Students are asked to provide clear answers in PDF format and are reminded that copying answers is prohibited. The assignment is due within a week.

Uploaded by

Mohamad Mahdi Swaidan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
53 views

Mohammad Mahdi Swaidan

This document contains an assignment for a computer science course on algorithms. It includes 7 questions covering topics like analyzing time complexities of functions, solving recurrence relations, and analyzing algorithms. Students are asked to provide clear answers in PDF format and are reminded that copying answers is prohibited. The assignment is due within a week.

Uploaded by

Mohamad Mahdi Swaidan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 10

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 = a.size();
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 =a.size()
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);
System.out.print(N);
Test(N/3);
System.out.print(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 ++ )
System.out.println(j, i);
for( int k = n; k > 1; k = k - 2)
System.out.println(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)
{ System.out.println(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++)
System.out.println(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);
System.out.print(v + "-"); }

What is printed by the call mystery (-5). Show your tracing?

mystery (-5)

 if(v<0) // true

mystery(v+2);

System.out.print( -5 + "-");

 mystery(-3)

 if(v<0) // true

mystery(v+2)

System.out.print(-3 + "-");

 mystery (-1)  if(v<0) // true

mystery(v+2)

System.out.print(-1 + "-");

 mystery (1)  if(v<0) // false

System.out.print(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 || first.equals(“”))
return second;
else
if (second == null || second.equals(“”)) return
first;
else
if(first.charAt(0) < second.charAt(0))
return first.charAt(0) + method( first.substring(1, first.length()), second);
else
return second.charAt(0) + method(first, second.substring(1,
second.length())); }

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

You might also like