LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034
M.Sc. DEGREE EXAMINATION – COMPUTER SC.
FIRST SEMESTER – NOVEMBER 2012
CS 1810 – DESIGN & ANALYSIS OF ALGORITHM
Date : 01/11/2012 Dept. No. Max. : 100 Marks
Time : 1:00 – 4:00
Section – A
Answer all Questions: (10 X 2 == 20 Marks)
- What do you mean by exact and approximation algorithm?
- Write about pseudo code.
- Define Adjacency Matrix Give example.
- What is Binary Search Tree Give example?
- Define Binomial coefficient.
- Differentiate between Greedy and Dynamic programming method.
- Define subset sum problem.
- Define Hamiltonian circuit give example.
- What do you mean by tractable and intractable?
- What do you mean by graph coloring?
Section – B
Answer all Questions: (5 X 8 == 40 Marks)
11 a) Explain Mathematical analysis for recursive algorithms.
Or
- b) Write about Asymptotic notations and analysis.
12 a) Write an algorithm to perform binary search trace out with suitable
Example.
Or
- b) Explain with example how matrix multiplication is performed using
Strassen’s .
- a) Explain about Optimal Binary Search Tree Algorithm.
Or
- b) Explain with example the Knapsack problem.
- a) Write an algorithm to solve N-Queen problem.
Or
- b) Write an algorithm to solve Subset sum problem.
- a) Write an algorithm for NP Hard problem.
Or
- b) Write about the approximation algorithm for Travelling Salesman Problem.
Section – C
Answer any TWO Questions: (2 X 20 == 40 Marks)
- a) Explain the two different algorithms for finding out GCD.
- b) Compare Merge sort with Quick sort.
- a) Write about the Kruskal’s algorithm and give example.
- b) Explain in detail about memory functions.
- a) Explain in detail the subset sum problem algorithm.
- b) Explain the Approximation algorithm for NP – Hard problem.