MCA-12
December Examination 2016
MCA IInd Year Examination
Design and Analysis of Algorithm
Paper MCA-12
Time 3 Hours Max. Marks 80
Note: The question paper is divided into three sections B and C. Write answers as per given instructions.
Section A 8 × 2 16
(Very Short Answer Questions)
Note: Answer all questions. As per the nature of the question delimit your answer in one word, one sentence or maximum upto 30 words. Each question carries 2 marks.
What is the time complexity of Binary search algorithm for best, average and worst case?
What are the factors on which efficiency of an algorithm depends?
Define space complexity.
What are asymptotic notations? Name all.
Divide and conquer algorithm is applied in a problem when sub-problems are of which type?
What is greedy strategy for knapsack problem?
594
MCA-12 200 3 (P.T.O.)
MCA-12 200 3 (Contd.)
594
What is minimum spanning tree?
(viii) What are the two classes of NP-problem?
Section B 4 × 8 32
(Short Answer Questions)
Note: Answer any four questions. Each answer should not
exceed 200 words. Each question carries 8 marks.
On what kind of input does the Quick sort algorithm exhibit its
worst case behaviour? Why?
State and proof Cook's theorem.
Show that travelling salesman problem in NP-Complete.
What are the advantages of dynamic programming approach
over divide and conquer approach and greedy approach?
Define how knapsack problem is solved by using dynamic
programming approach.
Explain 4 Queens and 8 Queens Problem.
Which one is better in term of space complexity, Quick sort or
Merge sort? Justify your answer.
Explain job sequencing problem with deadlines. How it can
solved by Greedy approach.
MCA-12 200 3
594
Section C 2 × 16 32
(Long Answer Questions)
Note: Answer any two questions. You have to delimit your each
answer maximum upto 500 words. Each question carries
16 marks.
10) What is the significance of using notations in analysis of
algorithms? Explain various notations in brief.
11) Explain the heap operation and Heap sort. Illustrate the
operation of heap and sort the following array:
A 13, 25, 17, 20, 4
12) Find minimum spanning tree using prim's and kruskal's
algorithm.
13) Solve the travelling salesman problem having the following
cost matrix, using branch and bound technique.
∞ 20 30 10 11
15 ∞ 16 4 2
3 5 ∞ 2 4
19 6 18 ∞ 3
16 4 7 16 ∞