Design and Analysis of Algorithm 2017- MCA 2nd year AKTU

Printed Pages: 02 Sub Code: RCA303

M.C.A.
(SEM III) THEORY EXAMINATION 2017-18
DESIGN & ANALYSIS OF ALGORITHM

Time: 3 hours Max Marks: 70

Note: 1. Attempt all Sections. If require any missing data; then choose suitably.
2. Any special paper specific instruction.

SECTION A

1.  Attempt all questions in brief. 2 x 7 = 14

a.  Differentiate between asymptotic notation O and Ω.
b.  Write all the 3 cases of master method to solve the recurrence T (n): aT(n/b) + f(n).
c.  Solve the 4-queen problem using backtracking technique and find.
d.  Why Dijkstra and Bellmen-Ford algorithm are differ from each other? Even both are single source shortest path.
e.  What do you mean by augmenting data structure?
f.  Define P, NP and NP-complete class of problem. Write three problems which are NP-complete.
g.  Explain randomized algorithm with the help of an example.

SECTION B

2.  Attempt any three of the following. 7 x 3 =21

a.  Sort the following sequence of input using heap sort: {10, 2, 1, 5, 3, 8, 11, 24, 7}. Also discuss the average and worst case complexities.
b.  Differentiate between backtracking and Branch and Bound approach. Write an algorithm for sum subnet problem using back tracking approach. Find all possible solution for following instance using same if M:35, S:<1, 2, 5, 7, 8, 10, 15, 20, 25 >.
c.  Define the single source shortest path problem. Write an algorithm for single source shortest path problem where graph is having negative weight edges and also apply the same on following graph.

d.  Discuss the kruskal’s algorithm and find the minimum cost spanning tree of the following graph:

e. Construct the string matching automation algorithm for the pattern P = aabab and illustrate its operation on the text string:

T=aaababaabaababaab

SECTION C

3. Attempt any one part of the following: 7 x 1 = 7

(a)  Write the algorithm of Quick sort and using master method to give an asymptotic tight solution to the recurrence.
T(n)=4T(n/2)+n2√n
(b)  Prove that a red black tree with n internal nodes has height a most 2log(n+1).

4. Attempt any one part of the following: 7 x 1 = 7

(a)  Derive a relation between degree and the height of n keys B-tree.
Insert the following information F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E into an empty B-Tree with degree t=3.
(b)  Design a recursive solution to the Longest Common Subsequence (LCS) problem.
Determine an LCS of (22112121) and (211221121).

5. Attempt any one part of the following: 7 x 1 = 7

(a)  Write an algorithm for chain matrix multiplication. Calculate the minimum number of multiplication required to compute the chain A1 A2 A3 A4 A5 for matrix where A1=2×3, A2=3×4, A3=4×5, A4=5×3, A5=3×4.
(b)  What do you mean by greedy algorithm? Write greedy algorithm for Huffman code. Show that your algorithm has greedy choice property.

6. Attempt any one part of the following: 7 x 1 = 7

(a) Describe Branch and Bound technique. How the branch and bound technique can be used to solve the Traveling Salesman Problem?
(b) Write the sort note on following with examples:

i. Graph Coloring
ii. N-Queen Problem
iii. Hamiltonian Cycles
iv. Sm of subsets.

7. Attempt any one part of the following: 7 x 1 = 7

(a) Define string matching problem and describe any string matching algorithm with suitable example.
(b) Write short notes on any two of the following:

(i) Randomized algorithms
(ii) Matrix operations
(iii) Fast Fourier Transform