Madras University (UnOM) 2006 M.C.A Computer Aplications Algorithm Analysis & Design - Question Paper

Time: 3 hours
Maximum: 75 marks

PART A - [5 x five = Marks 25]
ans ALL ques..
All ques. carry equal marks.

1. (a) What do you understand by Divide and Conquer strategy?

Or

(b) discuss selection sort with an example.

2. (a) discuss the Time Vertex Splitting issue.

Or

(b) What is Dynamic Programming9 elaborate its applications?

3. (a) Briefly explain the general backtracking method.

Or

(b) Write a n ote on sum of subsets issue and its solution.

4. (a) define the Branch-and-Bound Search method.

Or

(b) elaborate Algebraic Manipulations? discuss.

5. (a) explain the use of Comparison Trees for deriving lower bounds in sorting.

Or

(b) elaborate NP-Hard and NP-complete classes.

PART B - [5 x 10 = Marks 50]
ans any 5 ques..
All ques. carry equal marks.

6. Develop a straight forward algorithm and a recursive algorithm to determine the maximum and minimum items in a set of n elements.

7. explain the space and time-complexity of algorithms with illustrative examples.

8. discuss the Greedy Method and its application to a specific issue.

9. define the knapsack issue and a Branchand-Bound algorithm for its solution.

10. explain how the reachability issue in a graph is tackled by Breadth 1st search.

11. explain in detail the string editing and the graph colouring issues.

12. define the travelling salesperson issue and an algorithm for its solution.

13. discuss the basics of (a) Lower Bound Theory and (b) Lower Bounds through reductions.

Earning:   Approval pending.