undefined
DR. BABASAHEB AMBEDKAR TECHNOLOGICAL
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.
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