Loyola College M.Sc. Computer Science Nov 2010 Design & Analysis Of Algorithm Question Paper PDF Download

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)

 

 

  1. What do you mean by Worst case efficiency?
  2. Write about Time efficiency?
  3. Define Adjacency Matrix Give example?
  4. What is Binary Search Tree Give example?
  5. Write the formula of finding optimal solution for the binomial equation?
  6. Differentiate between Greedy and Dynamic programming method?
  7. Define state space tree Give example?
  8. Define Hamiltonian circuit give example?
  9. Define Recursion?
  10. 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

  1. b) Write about different problem types which are used in

algorithm design   and analysis?

 

12  a)          Discuss Quicksort with example?

Or

  1. b) Explain with example how matrix multiplication is performed

using  Strassen’s ?

 

  • a) Explain about Warshall’s algorithm?

Or

  1. b) Explain with example the Knapsack problem?

 

 

 

 

  • a) Write an algorithm to solve N-Queen problem?

Or

  1. b) Write an algorithm for Hamiltonian circuit problem?

 

  • a) Write an algorithm for NP Hard problem?

Or

  1. 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?
  1. b) Explain with example the Prim’s algorithm?

 

  • a) Write about the Dijikstra algorithm and give exanple?
  1. 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?
  1. b) Explain the Approximation algorithm for NP – Hard problem?

 

 

Go To Main page

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

© Copyright Entrance India - Engineering and Medical Entrance Exams in India | Website Maintained by Firewall Firm - IT Monteur