D D1874 Pages: 2

Reg No.: Name:
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
FIRST/THIRD SEMESTER MCA DEGREE EXAMINATION, JULY 2018
Course Code: RLMCA207
Course Name: DESIGN AND ANALYSIS OF ALGORITHMS

Max. Marks: 60 Duration: 3 Hours
PARTA Answer all questions, each
carries 3 marks Marks
1 What is meant by the time complexity of an algorithm? Explain with an example.
(3)
2 Explain Strassen’s method for matrix multiplication. (3)
3 Explain the control abstraction for greedy strategy. (3)
4 Compare and contrast between divide and conquer and dynamic programming (3)
5 Differentiate between depth first and breadth first tree in branch and bound (3)
method.
6 What are bounding functions? (3)
7 What is control abstraction for backtracking? (3)
8 Compare P and NP classes of algorithms. (3)
PART 8

Answer six questions, one full question from each module and carries 6 marks

Module I
9 With suitable examples, explain various methods of solving recurrence (6) equations.
OR
10 Explain Asymptotic notations and their properties with a suitable example. (6)
Module 1
11 Write the algorithm for merge sort and sort the following elements 50,30,80,5,90 (6)
using merge sort.
OR
12 Write the algorithm for Quick Sort and sort the elements 50,30,80,5,90 using (6) quick
sort.
Module III
13 Obtain the minimum cost spanning tree of the below graph using Kruskal’s (6)
algorithm.

Page 1 of 2