CS2251 Design and Analysis of Algorithms Nov/Dec 2014 Question Paper

[DhilipPrabakaran]

   

Question Paper Code : 91343

B.E. / B.Tech. DEGREE EXAMINATION, NOVEMBER / DECEMBER 2014.

Fourth Semester

Computer Science and Engineering

CS 2251 / CS 411 CS 1251/080230013/10144 CS 402 DESIGN AND ANALYSIS OF ALGORITHMS

(Regulation 2008/2010)

(Common to PTCS 2251/10144 CS 402 - Design and Analysis of Algorithms for B.E. (part - Time) Third Semester - Computer Science and Engineering - Regulation 2009/2010)

Time : Three hours
Maximum: 100 marks

Answer ALL questions.
PART A - (10 x 2 = 20 marks)
1. Define theta notation.
2. What is meant by substitution method?
3. Differentiate linear search and binary search techniques.
4. Define knapsack problem.
5. What is meant by principle of optimality?
6. Define cost of a tour.
7. Differentiate live and dead nodes.
S-. What is a Hamiltonian cycle?
9. State the difference between FIFO and LC branch-and-bound algorithms.
10. Where do you apply problem reduction method?

PART B (5 x 16 = 80 marks)
11. (a) DISCUSS the properties of big Oh notation.
Or
(b) With an example, explain how recurrence equations are solved.

12. (a) Explain binary search algorithm with an example. (16)
Or
(b) Write down the algorithm for merge sorting. Explain how the following elements get sorted. (16)
(310, 285, 179: 652, 351, 423, 861, 254, 450, 520)

13.(a) (i) Explain multistage graphs with an example. (8)
(ii) Write notes on optimal binary search trees. (8)

Or

(b) Consider the Travelling Salesperson instance defined by the following cost matrix.
(Attachment the Question Paper to view the Image)

Draw the state space tree and show the reduced matrices corresponding to each of the. node. (16)

14. (a) Explain 8 Queens problem, with an example. (16)
Or
(b) Explain graph coloring with the following graph. (16)

15. (a) Write notes on Connected components and Spanning trees (16)
Or
(b). Consider the knapsack iristance n = 3, (w l, w2, w3) = (2,3,4), (p1, p2, p3) = (1,2,5) and m = 6. Explain 0/1 knapsack algorithm to solve the above
instance. (16)

Full Name : Dhilip Prabakaran
College Name : Dhanalakshmi College of Engineering
Department : Computer Science and Engineering
Semester : 4
Subject Code : CS2251
Subject Name : Design and Analysis of Algorithms
Study Material Description : Question Paper of CS2251 Design and Analysis of Algorithms November December 2014.

Attachment :
  DAA Nov Dec 2014 QP V+.pdf (Size: 932.63 KB / Downloads: 2,930)

[Srini]

Good Job bro... +3