MCA-12
June 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.
Define time and space complexity.
What are searching algorithms?
Explain the need of Analysis of Algorithm.
What is divide and conquer strategy?
Explain the concept of backtracking.
Define a Hamiltonian Cycle.
What is the requirement of branch and bound techniques?
(viii) What is reducibility?
594
MCA-12 200 3 (P.T.O.)
MCA-12 200 3 (Contd.)
594
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.
Explain Knapsack problem with an example.
Explain the flow shop scheduling.
Write briefly about sets and disjoint sets.
Explain, what optimal binary search tree is?
Explain the characteristics of dynamic programming.
What are NP-hard and NP-Complete problem classes?
Explain the solution of 8-Queen's problem.
Use the master method to give tight asymptotic bounds for
the following recurrences.
T n.
T n2.
T n3.
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) Explain the NP-Complete Algorithm. Prove that formula
satisfiability is an NP Complete problem.
11) Explain the Merge-sort Algorithm with suitable example.
Analyze the time complexity of the Merge Sort algorithm
(Worst, Best and Average Case).
12) What is greedy approach of problem solving? Explain
Knapsack Problem.
13) Explain the quick-Sort Algorithm with suitable example.
Analyze the time complexity of the Quick sort algorithm
(Worst, Best and Average Case).