undefined

DR. BABASAHEB AMBEDKAR TECHNOLOGICAL

UNIVERSITY LONERE – RAIGAD -402 103

Semester Examination – Summer - 2019

---------------------------------------------------------------------------------------------

Branch: Computer Engineering

Sem.:- IV

Subject and Subject Code:- Design and Analysis of Algorithms (BTCOC401)

Date:- 14/05/2019

Marks: 60

Time:- 3 Hrs.

=

=====================================================

Instructions to the Students

1

2

3

. Each Question carries 12 marks.

. Attempt Any Five Questions of the following.

. Illustrate your answers with neat sketches, diagram etc., wherever

necessary.

4

. If some part or parameter is noticed to be missing, you may appropriately

assume it and should mention it clearly.

_

_____________________________________________________________

Q.1. Attempt Any Three from the following questions. (04*03=12)

a) Define Big O notation? What is total time complexity of following code ?

int a,b,c,d,i.

{

for (i = 0 ;i<=11; i++)

{

a = a+b;

}

d= c+a;

}

b) Define algorithm. What is the need of algorithm analysis ? Which factors affect

runtime of algorithm?

c) Solve the following recurrence relation using characteristic polynomial.

n

if n=0 or n=1

t_{n }=

t _{n}_{-}_{1} + t_{ n}_{-}_{2} , otherwise

d) Solve the following recurrence using master method. Verify solution using

substitution method.

T(n) = 2T (n/2) + cn

3

D07E6E1D9ECEFE9FCC585CDAAC8AF06

undefined

Q.2.Attempt the following questions

(06*02=12)

a) Write an algorithm of merge sort and illustrate the operation on an array

using Merge Sort.

A={5

2

4

7

1

3

2

6}

b)Multiply following two matrices using Strassen’s matrix multiplication

algorithm.

Matrix A = 1

Matrix A = 1

2

Matrix B=

Matrix B=

5

6

2

5

6

3

4

7

8

Q.3. Solve the following questions

a) What is Greedy method? Explain elements of Greedy method.

(06*02=12)

b) Construct an optimal instance of Huffman Code for the following set of

frequencies using Greedy method.

“a” “b” “c” “d” “e” “f”

Frequency

4

5

13 12 16

9

5

Q.4. Solve the following questions:

(06*02=12)

a) Determine longest common subsequence using dynamic programming approach

for X and Y. What is the length of longest common subsequence?

X = < A, B, C, B, D, A, B > Y = < B, D, C, A, B, A >

b) Find the shortest path using Bellman Ford algorithm for the following graph.

Note that vertex z is source vertex.

3

D07E6E1D9ECEFE9FCC585CDAAC8AF06

undefined

a) Solve the following 15-Puzzle Problem.

b) How 4- Queens problem is solved by backtracking approach? Explain with the

help of state space tree.

a) Explain Class P, Class NP and Class NPC problems in detail.

b) Insert the following keys into empty B-Tree with minimum degree 2. Show the

configuration of B-Tree after each insertion operation.

Keys: F S Q K C L H T V W M R N P A B X Y D Z E

c) What do you mean by Red Black Tree?. What are the characteristics of Red

Black tree?

d) Explain Polynomial time reduction with example.

*

*********************

3

D07E6E1D9ECEFE9FCC585CDAAC8AF06