# 2005 M C A Design and Analysis of Algorithm Question paper

** University Question Papers **

**
**2005 M C A Design and Analysis of Algorithm Question paper

END-TERM EXAMINATION

Third Semester [MCA] - DECEMBER 2005

Paper Code: MCA 205 Subject: Design and Analysis of Algorithm

Time: 3 Hours (Batch-2004) Maximum Marks: 60

Note: Attempt five questions in all, including Q. 1 which is compulsory.

Q. 1. (a) Given three functions (n!, nn and 22n), which has the largest growth rate

and which the smallest? 2

(b) Is merge sort a stable sorting algorithm? Justify your answer. 2

(c) What is the similarity and difference of dynamic programming and divide-

and-conquer? 2

(d) Will either Kruskal’s or Prim’s algorithm work correctly on graphs that

have negative edge weights? 1

(e) When a problem is said to be polynomially reducible? 1

(f) What is an optimal binar y search tree? 1

(g) What is a Huffman tree? 1.5

(h) What are the time complexities of Quick Sort? 1.5

Q.2. (a) Explain the various asymptotic notations used to analyze an algorithm. 5

(b) Solve the recurrence relation for the no. of key comparisons made by merge

sort in the worst case. (You may assume that n =2 k). 4

(c) Define Master Theorem. 3

Q.3. (a) Design a H (n2 ) algorithm for finding an optimal binary search tree. 6

(b) Consider the problem of sch eduling n jobs of known duration’s t1, t2, …… ..

tn for execution by a single processor. The jobs can be executed in any order,

one job at a time. You want to find a schedule that minimizes the total time

spent by all the jobs in the system. Design a Greedy algorithm for this problem.

(The time spent by one job is the sum of waiting time and ex ecution time). 6

Q. 4 (a) Apply Kruskal’s algorithm to find a minimum spanning tree of the

following graph. 5

1

6 6

5

3 4 6

6 6 6

6 2

(b) Prove the correctness of Kruskal’s algorithm. 5

(c) Define disjoint subsets. 2

Q.5 (a) Give an O (V+E)-time algorithm to compute the component graph of a

directed graph G = (V, E). Make sure that there is at most one edge between

two vertices in the component graph your algorithm produces. 6

(b) Let Ax = b be a system of m difference constraints in n unknowns. Show

that the Bellman-Ford algorithm, when run on the corresponding constraints

graph, maximizes S xi subject to Ax = b and xi = 0 for all x i 6

i =1

Q.6 (a) Explain Rabin-Karp algorithm for string matching. What is its worst

case running time? 6

(b) What do you mean by string-matching automata? Write a pseudo code to

compute the transaction function d from a given pattern P [1…..m]. 6

Q.7. (a) Show that the class P, viewed as a set of languages, is closed under

union, intersection, concatenation, complement. 6

(b) A clique in an undirected graph G= (V, E) is a subset V’CV of vertices, each

pair of which is connected by an edge in E. The size of a clique is the no. of vertices it

contains. The clique problem is the optimization problem of finding a clique of

maximum size in a graph. Prove that the clique problem is NP-complete. 6

Q.8. Write notes on following:- 12

(i) Strassen’s algorithm for Matrix Multiplication

(ii) The Knuth-Morris-pratt algorithm.

(iii) Strongly connected components.