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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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)

 

1. What do you mean by exact and approximation algorithm?
2. Write about pseudo code.
3. Define Adjacency Matrix Give example.
4. What is Binary Search Tree Give example?
5. Define Binomial coefficient.
6. Differentiate between Greedy and Dynamic programming method.
7. Define subset sum problem.
8. Define Hamiltonian circuit give example.
9. What do you mean by tractable and intractable?
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 Asymptotic notations and analysis.

 

12  a)   Write an algorithm to perform binary search trace out  with suitable

Example.

Or

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

Strassen’s .

 

• a) Explain about Optimal Binary Search Tree 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 to solve Subset sum 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) Compare Merge sort with Quick sort.

 

• a) Write about the Kruskal’s algorithm and give example.

1. b) Explain in detail about memory functions.

 

• a) Explain in detail the subset sum problem algorithm.

1. b) Explain the Approximation algorithm for NP – Hard problem.

 

 

Go To Main page