LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034
M.Sc. DEGREE EXAMINATION – COMPUTER SCIENCE
FIRST SEMESTER – NOVEMBER 2010
CS 1810 – DESIGN & ANALYSIS OF ALGORITHM
Date : 30-10-10 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 Worst case efficiency?
- Write about Time efficiency?
- Define Adjacency Matrix Give example?
- What is Binary Search Tree Give example?
- Write the formula of finding optimal solution for the binomial equation?
- Differentiate between Greedy and Dynamic programming method?
- Define state space tree Give example?
- Define Hamiltonian circuit give example?
- Define Recursion?
- 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 different problem types which are used in
algorithm design and analysis?
12 a) Discuss Quicksort with example?
Or
- b) Explain with example how matrix multiplication is performed
using Strassen’s ?
- a) Explain about Warshall’s algorithm?
Or
- b) Explain with example the Knapsack problem?
- a) Write an algorithm to solve N-Queen problem?
Or
- b) Write an algorithm for Hamiltonian circuit 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) Explain with example the Prim’s algorithm?
- a) Write about the Dijikstra algorithm and give exanple?
- b) Solve the knapsack using Branch and Bound Technique?
- a) Solve the following set s={1,2,5,6,8} d=9 using subset sum problem algorithm?
- b) Explain the Approximation algorithm for NP – Hard problem?