Madras University (UnOM) 2005 M.Sc Computer Science design and analysis of algorithm - Question Paper

PART A - (5 x two = 10 marks)

ans ALL ques.. All ques. carry equal marks. every ans should not exceed 50 words.



1.What is sorting? Searching? Traversing?

2.Define optimality. Feasibility.

3.What is a directed graph? Biconnected component?

4. Write the constraints of a travelling sales man issue.

5.What do you mean by polynomial time algorithm?



PART B - (4 x five = 20 marks)

ans any 4 ques.. All ques. carry equal marks.

every ans should not exceed 250 words.



6. What is big-oh notation? How do you measurepractical complexities?

7. Write algorithm for quick sort.

8.What is right justified and write on string editing?

9. What is Hamiltonian cycle? Write algorithm for finding Hamiltonian path.

10. elaborate randomized algorithms? provide an example for illustration.

11.What is a comparison tree? discuss.



PART C - (5 x 10 = 50 marks)

ans ALL ques..

All ques. carry equal marks. every ans should not exceed 500 words.



12. (a) define divide and conquer principle. How this is used in finding maximum and minimum in an array?

Or

(b) Write briefly on recursion? Indirect recursion? How do you apply recursion in the process of computing factorial of a number? How complexities are calculated for recursive algorithm?



13. (a) Write algorithm and discuss for Strassen's matrix multiplication.

Or

(b) Using Greedy approach, discuss the job

sequencing issue with deadlines.



14. (a) What is Single source shortest path? How do you obtain 1 such path? explain how dynamic programming concept is applied.

Or

(b) discuss BFS and DFS Where they are applied? explain their algorithms.



15. (a) Using back tracking approach, discuss graph coloning issue.

Or

(b) discuss Branch and Bound principle. How this principle is used for solving travelling sales man problem?



16. (a) discuss briefly on lower bound theory and lower bound through reduction.

Or

(b)Write short note on :(i) Np hard and Np completeness (ii) Primality testing.

Earning:   Approval pending.