D D7420
Page 1 of 2
Total Pages: 2
Reg
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
THIRD SEMESTER MCA DEGREE EXAMINATION, DECEMBER 2017
Course Code: RLMCA207
Course Name: DESIGN AND ANALYSIS OF ALGORITHMS
Max. Marks: 60 Duration: 3 Hours
PART A
Answer all questions, each carries3 marks.
1 What is an algorithm? Explain its characteristics.
2 Write down control abstraction for divide and conquer method.
3 Explain the control abstraction for greedy strategy.
4 What is the principle of optimality in the theory of dynamic programming?
5 Write down DFS algorithm.
6 State sum of subset problem.
7 Explain the concept of branch and bound strategy.
8 Distinguish between deterministic and non deterministic algorithm.
PART B
Answer six questions, one full question from each module and carries6 marks.
Module I
9 Explain time and space complexity with relevant examples.
OR
10 What are asymptotic notations? Briefly explain their properties.
Module II
11 Write down an algorithm for finding minimum and maximum element in a list of
numbers. Explain the concept with an example.

OR
12 Explain the concept of merge sort algorithm with example.
Module III
13 Define minimum cost spanning tree.
Explain Prim's algorithm for finding MST.
OR
14 Explain Knapsack problem. Find out the optimal solution for the following 3 items
P2, P3) (500,900,700) and W2, . Knapsack capacity is 5. Also write
down the Knap sack algorithm.

D D7420
Page 2 of 2
Module IV
15 If we are given a directed graph G with n vertices. Explain how will you find out
the length of the shortest path between any pair of vertices in G. Justify your
answer with an example.

OR
16 What is dynamic programming? Explain how this concept is applied to solve
travelling salesman problem.

Module V
17 Explain how queen's problem is solved using the concept of backtracking.
OR
18 Explain N2-1 puzzle problem in detail.
Module VI
19 Explain NP-Hard and HP-complete classes.
Explain Clique problem.
OR
20 Prove that the travelling sales person problem is NP-complete.