2005 M C A Design and Analysis of Algorithm Question paper for exam preparation. Question paper for 2005 M C A Design and Analysis of Algorithm Question paper, 2005 M C A Design and Analysis of Algorithm Question paper. SiteMap
K2Questions Logo

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.


About us | SiteMap | Terms of use | Privacy Policy | Disclaimer | Contact us | ©2010 K2Questions.com

2005 M C A Design and Analysis of Algorithm Question paper for exam preparation. Question paper for 2005 M C A Design and Analysis of Algorithm Question paper, 2005 M C A Design and Analysis of Algorithm Question paper