algorithm

WRITTEN ASSIGNMENT 1

Question 1 (15 marks)

For each pair of f(n) and g(n) below, decide if f(n) = O(g(n)), f(n) = Ω(g(n)), or f(n) = Θ(g(n)). Note that more

than one of these relations may hold for a given pair; list all correct ones.

(a) f(n)= /span>+,g(n)= .

(b) f(n)=/span>2+3, g(n)=Σ/span>=1.

(c) f(n)=2, g(n)=3/span>.

(d) f(n)=2, g(n)=/span>!.

(e) f(n)=(/span>!) and g(n)=.

Question 2 (15 marks)

Solve the following recurrence relation into an expression of n. Show the detail steps for your derivatation.

Results without derivations do NOT receive any marks

T(n)={2/span>(/span>2)+/span>, when /span>>1 1, when /span>=1

Question 3 (30 marks)

Read the following program and calculate their computational cost as a function of n. For simplicity,

you can always assume that n is a power of 2.

- Give the tightest possible bound for the Big-O runtime complexity in terms of the input parameter n for each

of the following function.

- Show the detail steps for your derivatation. Results without derivations do NOT receive any marks

(a)

int tsum (int n){

int sum = 0;

for (int i = 1; i <= n; i *= 2)

sum += i * i * i;

return sum;

}

(b)

int tsum (int n){

if (n <= 0)

return 0;

return tsum (n /2)+ n*n*n;

}Question 4 (25 marks)

Suppose we have the following recursive function in C:

(a) What is the returned value of fib(5)?

(b) Suppose the time cost for fib(n) is T(n), write down the recurrence relation for T(n).

(c) Analyze the time cost for the recursive function in big-oh (O) notation.

(d) Rewrite this function in C which gives exactly the same output and make it of lower complexity. Analyze

the time cost for your new function in big-oh (O) notation.

int fib (int n) {

if (n <= 0 )

return 0;

if( n == 1 )

return 1;

return fib(n-1) + fib(n-2);

}

Question 5 (15 marks)

Suppose that each row of an n×n matrix A consists of 1's and 0's such that, in any row of A, all the 1's come

before any 0's in that row.

(a) Describe a method running in /span>(/span>) time (not /span>(/span>2) time) for finding the row of A that contains the most 1’s

(If more than two rows have the same number of 1’s, return the row with smallest row index). Use either C code

or pseudo-code.

(b) Analyze your algorithm and prove that the algorithm runs in /span>(/span>) time.