# 2005 Madras University M Sc Computer Science design and analysis of algorithm Question paper

** University Question Papers **

**
**2005 Madras University M Sc Computer Science design and analysis of algorithm Question paper

PART A - (5 x 2 = 10 marks)

Answer ALL questions. All questions carry equal marks. Each answer 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 problem.

5.What do you mean by polynomial time algorithm?

PART B - (4 x 5 = 20 marks)

Answer any FOUR questions. All questions carry equal marks.

Each answer 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. What are randomized algorithms? Give an example for illustration.

11.What is a comparison tree? Explain.

PART C - (5 x 10 = 50 marks)

Answer ALL questions.

All questions carry equal marks. Each answer should not exceed 500 words.

12. (a) Describe 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 computed for recursive algorithm?

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

Or

(b) Using Greedy approach, explain the job

sequencing problem with deadlines.

14. (a) What is Single source shortest path? How do you find one such path? Discuss how dynamic programming concept is applied.

Or

(b) Explain BFS and DFS Where they are applied? Discuss their algorithms.

15. (a) Using back tracking approach, explain graph coloning problem.

Or

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

16. (a) Explain 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.