algorithm answers

1. Algorithm for nth number in Fibonacci series

Read n

f1 <- -1

f2 <-1

i <- 0

while i<=n

f3 <- f1+f2

f1 <- f2

f2 <- f3

i <-i + 1

End while

Display f3


3. Recursive function to find the factorial

FUNCTION FACTORIAL (N: INTEGER): INTEGER



BEGIN

(* TEST FOR STOPPING STATE *)

IF N <= 0 THEN

FACTORIAL := 1

ELSE

FACTORIAL := N * FACTORIAL(N - 1)

END


4. If lim f(n)/ g(n) = 0 then f(n) = O(g(n))

n->∞ = ∞ then f(n) = ω(g(n))

= constant then f(n) = θ(g(n))

Here

Lim n+n logn/ n.n^(1/2) if we apply L hoptial’s rule we get 0, therefore

n->∞

n+n log n = O (n.n^(1/2))

In this way computing the limit helps us in comparing the order of growth of 2 specific function.


5. Algorithm to find the number of binary digits

Recursive procedure:

Function F(X: integer)

{

If X= =0 or X= = 1 Then

Return 1;

Else

Return 1+ F(X/2);

}

End Function

Analysis:

T(n) = 1 + T(n/2)
solving we get T(n)=0(nlogn)

6. Linear search – In class notes


7. Algortihm for multiplication of two matrices

MATRIX-MULTIPLY(A, B)

1 n ← rows[A]

2 let C be an n × n matrix

3 for i ← 1 to n

4 do for j ← 1 to n

5 do ci j ← 0

6 for k ← 1 to n

7 do ci j ← ci j + aik · bkj

8 return C


8. substituting n = 2k we get the roots as 2,2,1 and the time complexity as O(n log n)



9. There are two possible solutions, ω(n2 ) or O(n3).


10. 1. Algorithm computes sum of squares of 1 to n numbers.

2. Basic operation(inside for loop)
3. basic operation executed n times.
4. Efficiency class – O(n)

source: viveks blog