Anna University Coimbatore 2010-4th Sem B.E ./B.Tech /e Design and analysis of algorithms - Question Paper

AKNA UNIVERSITY CO1MBAT0M 9 (. 10 TCH. DCOftEE eUAWUMiONS . WAV / AMfe W REO<JLAT>OW*; 200$

FOURTH SEMESTER :COPiTC(tSC(ENCe 4 CN0*NfUH6 CaC2300l3 - OESiON AND ANALYSIS OF ALGORITHMS TMt: i Hours    M* Ma*Vs , V

PART- A

AMStVET? Alt WESTfONS

f. Define G raph [ftng

2    vVni the durances between Binary tree ad Binary Search vea**

3. Wnjeh (yse 9f graph kfi suited fqr Blcerinected graph?

4    Wta are soytj used in Travefling Safaapa<vori

S. Gpve three lormJla tor 1 knap*cii problem m    vw Bountf?

$ Defoe Recmive eigorittvn

7    Write an algor #*0 for BFT

8    Difference between Static tree ana Dynamic tree.

9.    Define Hamlftor> cycle and give an exampia.

10.    Fjr>a tha order of n^a *An +1.

f 1. Co*ipa/ Dynamic progwwiirtfl and Branch and bound techniques

12.    WhatsNP-h?

13.    Store the principle erf backioekirtg.

M. Wife iJowrt tfw adpacocy rntfff* for W* Idkwrng gnftx

**- Wirt* any *** eiut* ttt)*

¹ ?    Wia If Spanning tr**?

   OJv tfi raeunence f-auaiior for the w:r un birsivio* of mrg Wt

f9    DHn* <***\arr*: pfg>uiii>09-

20    Wt<ttfrio0*WBC#P'Cff*tiA9rfc| nA piomrto

PARTe

(S xA2* SO MARKS)

AN9WER ANY FIVE QUESTIONS

21 a) Apptf t*efcD9ck*g    9> *>ive tM ttkwm? tflifww* of tfte auosa e

sunproCMTi S*(I.3.4.5J    1.

W G*e short r*o*e* on urfdeodaNa proeJm. and NP*Comp*e profem

2? $o*e Ihe Wowing instance of (he knapsack problem by the branch and (jountf Tecrmique.

Bern Weight Value

f    10    $f00

2    7    <63 T*>eKnpsek'*Cpac#y W16

3    3    $55

4    4    $12

23 a} Write an ef0ori<hm to solve 0/1 fcn*ps#efc proWem using bram* and bou technique.

t) Discusp on divide end conquer strategy for multiplying two n*blt number*

4,    fer I-oM" rsblM    _%

_w 0¹e an    w    articulation peima ana to cgnMPJW eonnettQ e,

*5 %) 0/5CU9S the fonmenMl of analysis fiameMd    iam n 4

j/gonLbm defflfl.

Swwrtoiv in# qwie *o/t afjorWim torts tne following sen of keys-    ?

<1.1,11.1.11) W (5.SJ.3.f3i

?6. ) (Jst the rwry *^or analyzing ffiency of r%0v5>v e*9nthtn wiih an exampfa.

0) Writ* a recursive af$ortfrm tor the Tower of Hanoi puzzle. OWvin tfte recurrence Muatfon.

¹ 27. a; Write Merge eort afgorrtfim and efso calculate the Tirne complexity, ft) DtaOuta briefly about space and time trade offs

2$, 0) Wnte a genera) algorithm to find an opt)r el binary search tree

b) fixpla/n the Warshaff'l igoflthm for computing tha transitive closure crt directed graph

1

Attachment: anna-university-coimbatore-2010-b-e-764-1.JPG anna-university-coimbatore-2010-b-e-764-2.JPG anna-university-coimbatore-2010-b-e-764-3.JPG

Earning:   Approval pending.