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  
tn =  
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.  
Characters A1 A2 A3 A4 A5 A6  
“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