MCA III (Third) Semester Examination 2013-14

Course Code: MCA304 Paper ID: 0873204

Design & Analysis Algorithms

Time: 3 Hours Max. Marks: 70 Max Marks: 75

Note: Attempt six questions in all. Q. No. 1 is compulsory.

1. Answer any five of the following (limit your answer to 50 words). (4x5=20)

a) What do you understand by asymptotic notation? Explain each in brief.

b) Rank the following function by their order of growth.

(3/2)n, (2/3)n, 22^n, en, 2n!.

c) Solve the following recurrence relation.

Assume T(1)=1,T(3)=1

i)  T(n)= T(n/2)+T(n/3)+n

ii)  T(n)= 3T(n1/3)+log n

d) Can the Master method be applied to recurrence T(n)= 4T(n/2)+ n2logn?

e) Suppose that x is a node in a binomial tree with in a binomial heap, and assume that sibling[x] is not equal to nil. If x is not a root, how does degree [sibling[x]] compare to degree[x]. How about if x is a root?

f) What do you understand by non-deterministic problems? Discuss using a suitable example. Also discuss in detail about NP- Hard and NP – Complete problems

g) What are the prerequisites of the applicability of Dynamic Programming? Differentiate between Divide & Conquer and Dynamic Programming approach.

h) Illustrate the operation of COUNTING-SORT on the array A=[6,0,2,0,1,3,4,6,1,3,2].

2. Show that a Red Black Tree with n internal nodes has height at most 2lg(n+1). Discuss the different cases of insertion algorithm and construct an RB tree of element 41, 38, 31, 12, 19, 8, 45, 2, 0, 6. (10)

3. What is n-queen problem? Give its algorithm with example to show the step involved in solving the problem by using backtracking. (10)

4. Give an approximate algorithm for solving the following sum of subsets problem. N=4, target value (M) = 25, weight vector (w1, w2, w3, w4 ) = ( 10, 25, 5, 10 ). (10)

5. Explain and write an algorithm for Greedy Approach to an activity selection problem of scheduling several competing activities that require exclusive use of common resource, with a goal of selecting a maximum size set of mutually compatible activates. Also solve following problem. (10)

Activity / A1 / A2 / A3 / A4 / A5 / A6 / A7 / A8 / A9 / A10
Starting Time / 1 / 2 / 3 / 4 / 7 / 8 / 9 / 9 / 11 / 12
Finish Time / 3 / 5 / 4 / 7 / 10 / 9 / 11 / 13 / 12 / 14

6. Describe the single source shortest path algorithms. Differentiate between the working of Bellmen Ford and Dijkastra’s Algorithms. Also explain how BFS traversal algorithm works as single source shortest path solution for a graph having equal weight on all of its edges. (10)

7. Show the results of inserting the keys 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 minimum degree =2. Only draw the configuration of the tree just before some node must split. Draw the tree in the light of algorithm BTree-Insert(T, K), BTree-SplitChild(x, i, y) and BTree-Insert-NonFull(x, k).

You can assume that keys are entered in the given order. (10)

8. a) Show how to compute transitive closure of a graph using Floyd-Warshall’s for all pair shortest path. (5)

b) Give a dynamic programming solution for the sum of subset problem. Also analyze the complexity of the algorithm. (5)