My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
|
Download Model question papers & previous years question papers
|
Posted By: ashish Member Level: Diamond Posted Date: 26 Dec 2007
|
2005 M.C.A Design and Analysis of Algorithm Question paper
| Course: M.C.A |
|
University: |
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.
Return to question paper search
|
|
|
Submit Previous Years University Question Papers and make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.
|
Watch TV Channels
|