D D7420

Total Pages: 2
Reg No.: Name:

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. (3)

Write down control abstraction for divide and conquer method. (3)

Explain the control abstraction for greedy strategy. (3)

What is the principle of optimality in the theory of dynamic programming? (3)
Write down DFS algorithm. (3)

State sum of subset problem. (3)

Explain the concept of branch and bound strategy. (3)

ॐ ~ ಲಾ ~ ~+ ~ ‏تم‎

Distinguish between deterministic and non deterministic algorithm. (3)

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. (6)

OR
10 What are asymptotic notations? Briefly explain their properties. (6)
Module II
11 Write down an algorithm for finding minimum and maximum element in a list of (6)

numbers. Explain the concept with an example.

OR
12 Explain the concept of merge sort algorithm with example. (6)
Module III
13 a) Define minimum cost spanning tree. (2) b) Explain Prim’s algorithm for finding
MST. (4)
OR
14 Explain Knapsack problem. Find out the optimal solution for the following 3 items (01,

(6) 22, 23) = (500,900,700) and (W1, ۷۷2, W3)=(1,3,7) . Knapsack capacity is 5. Also write

down the Knap sack algorithm.

Page 1 of 2