D D1874 Pages: 2
Page 1 of 2
Reg
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
PART A
Answer all questions, each carries 3 marks Marks
1 What is meant by the time complexity of an algorithm? Explain with an example.
2 Explain Strassen's method for matrix multiplication.
3 Explain the control abstraction for greedy strategy.
4 Compare and contrast between divide and conquer and dynamic programming
5 Differentiate between depth first and breadth first tree in branch and bound
method.

6 What are bounding functions?
7 What is control abstraction for backtracking?
8 Compare P and NP classes of algorithms.
PART B
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
equations.

OR
10 Explain Asymptotic notations and their properties with a suitable example.
Module II
11 Write the algorithm for merge sort and sort the following elements 50,30,80,5,90
using merge sort.

OR
12 Write the algorithm for Quick Sort and sort the elements 50,30,80,5,90 using
quick sort.

Module III
13 Obtain the minimum cost spanning tree of the below graph using Kruskal's
algorithm.

D D1874 Pages: 2
Page 2 of 2
OR
14 Explain the job sequencing problem with a suitable example.

Module IV
15 Explain all pair shortest path algorithm with an example
OR
16 Explain travelling sales person problem with an example.
Module V
17 Explain sum of subsets problem with an example.
OR
18 Explain N2-1problem with an example.
Module VI
19 Compare SAT and 3-SAT problem.
OR
20 Explain vertex cover problem with relevant examples.