Scribd
Upload
206 views2 pages

(A) (B) (C) (D) (E) (0 (G) (H) (I) O Tree? 2. (A) Examples' (B) Elemlnts' To

This document appears to be an exam for a computer science and engineering course on design and analysis of algorithms. It contains 8 questions, with question 1 being compulsory and carrying 10 marks, and questions 2-7 carrying 15 marks each. Question 1 asks about basic algorithm concepts like definition of algorithm, divide and conquer, minimum spanning tree, decode tree, binary tree, biconnected component, dynamic programming, graph coloring, Hamiltonian cycle, and comparison tree. The other questions ask about algorithm analysis notations, merge sort, knapsack problem, binary search trees, queues problem, subsets summing to a number using dynamic programming, and traveling salesman problem.

Uploaded by

api-279049687
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
206 views2 pages

(A) (B) (C) (D) (E) (0 (G) (H) (I) O Tree? 2. (A) Examples' (B) Elemlnts' To

This document appears to be an exam for a computer science and engineering course on design and analysis of algorithms. It contains 8 questions, with question 1 being compulsory and carrying 10 marks, and questions 2-7 carrying 15 marks each. Question 1 asks about basic algorithm concepts like definition of algorithm, divide and conquer, minimum spanning tree, decode tree, binary tree, biconnected component, dynamic programming, graph coloring, Hamiltonian cycle, and comparison tree. The other questions ask about algorithm analysis notations, merge sort, knapsack problem, binary search trees, queues problem, subsets summing to a number using dynamic programming, and traveling salesman problem.

Uploaded by

api-279049687
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

:t

,,, }

Reg. No. :

136 S L2
*
FOUR YtrAR B.TtrCH. DEGREE trXAMINATION APRIL, 2016.

SIXTH SEMESTER EXAMINATION

COMPUTER SCIF]NCE AND ENGINEERING

DESIGN AND ANALYSIS OF ALGORiTHMS (DAA)


(scHEME * 2013)

Time: 3 Hours Max. Marhs : 70

euestion No. 1 is compulsory and it must be answer:ed first in sequence at


one place onlY.
Answer any FOUR from the remaining
questions carry 15 marks each'
Question No. 1 carries 10 marks and remaining

1. (a) What is an Algorithm?


(b) What is divide and conquer?
(c) Defi.ne minimum sPanning tree?
(d) Define d.ecod'e tree?
(e) What is binarY tree?
(0 Define biconnected comPonent?
(g) What is dYnamic Programming?
(h) Define graPh coloring?
(i) What is Hamiltonian cYcie?
O Define comParison tree? \

2. (a) Explain different Asymptotic notations with the help of examples'


(8)

(b) write routine for merge sort? Explain merge sort algorithm with the help
of following data elemlnts'
Q)

7,10,2,5,4,3,16, 18

to the knapsack instance =7, rn:15,


3. (a) Find an optimal solution (L

(8)
(2, 3, 5, 7 ,1,4,1)
(b) Find an optimal binary merge patterns for ten files whose lengths are
(7)
28,32,12,5,84,53,91,35,3 and 11'
Turn Over
4. (a) Explain different techniques for graphs with the help of u*r*pl"". (10)
(b) Write different properties of binary trees. (5)

5. Find an optimal binary search tree for n=4 the identifier set (o,, a2,as,aa)=
(cont, float, if, while) with P(1)= %o,P@)=y,n(a)=/ro,P@)=%o
q(0)= %, q{) = /ro, pu (z) = %,q(B) = %r, q(a) = %0. (15)

(a) Find one solution for the 4 queues problem? (5)

(b) Let W = {5,7 ,1$,12,15, 18, 20} and m = 35 . }-ind all possible subsets of ro
that sum to m. Da this using sum of sub. Draw the portion of the state
space tree that is generated. (10)

7. Consider the traveling salesperson instance defined by the cost matrix.


s7 312 8
3oc 6149
58 oo618
93 5 cc 11
18 14 I 8 0..;

(a) Obtain the reduced cost matrix. (5)

(b) Draw the dynamic state space tree approach. (10)

2 136 s 12

You might also like