DAA Solutions

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 this recurrence equation by substitution method I get the roots as 1 and 1 and the efficiency class as O(log n)

If it is solved by Master method again we get it as O(log n)..

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 = 2^k we get the roots as 2,2,1 and the time complexity as O(n log n)

9. There are two possible solutions, ω(n² ) or O(n³).

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)

Disclaimer - The solutions here need not be right.

Download the Solution