0 ratings 0% found this document useful (0 votes) 74 views 38 pages DAA Module 3
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content,
claim it here .
Available Formats
Download as PDF or read online on Scribd
Go to previous items Go to next items
Save DAA Module 3 For Later ah Mot oO
~ Mode Ty 6 oY
a edly Method
=| te Ba problers Selving
Jeahuieque thot aloous oie do fine! the optinet
Sabaknn (moninur oRaninimar). Consielerity one. fn
atadime north the hope thot we get an ops ina!
Seluf in,
“Teeknapenck obler +
Given 0 knapeacl of enpai ty
of weights WL, Wo, Ds,-= Wn wit pooldbs Pp, Pa,-’* Por |
4 ancl m obyeds
© choose only hose. abjeehs the aves aim ry
poblh. |
O-The toted cooght of selecleel objeats shoulel be Jers |
then on cata} to «0 (wm) |
”
PM onietre. PM |
dey |
y
WyXi NEXUS
gooltls (A, fr P= (85, 40, 207
voeights (Wy, ws,10s) = (Ie, 25°, 26)
abjost toi [Pi | wrk BS | pba xy py [RO =Re-wixx
4
wi
Joitia) | ole = 7 =40
Sep}} 1 }lolas| =I “TeOSs 35°
| ri i Ino = ho 30-251
Slep2} D2 126 |ho \ =o
0.908 W202 7. =Se20:
Shep? 3 00 130 = Breage IE WB0= FS P2ovOIS
lo =0
Proobils = 354 yor gs= BAS
Feacltury (24, 9, %6)= (1, 1, 025)
weight (toy, wares) = Co, 2g, 28)
Scanned with CamScanner 6)
© find Ory optima) Solutio chy the. knapsack Instance
N=, avel me 1S, (P, Po, Par =-Pr)=(10,55 15 7,6, 18,3)
(oy, 000, 3, Wy, Ud.
S, 4, 7)= (9,3,5, 9, 1,4,1)
6n= 55.35
© Considey thot thee me thee Hem, woe Orel
Probrts velue. of enrol ideny ts giren belo,
L_ [wi | Pi
| 18 | 30
w= 99
Is | ay
24.6 |
Silo) \6 Ans= Zes01 |
© fina ap opdima)
mz 22, &, Pao, Po,
Relidiv> dr the Enapseeck m23
- (5, 24, '5)8 eo, Wo, ws) = (18,15, 10)
Ons= Shs
Scanned with CamScanner @
® Dob Seo wendiog woth deodbines t
~The peoblern of job Sacer wort dead bines
ig delryed) on fadloos .
Giro a set of n pbs ote) aroetates wit
each gob j 1s an Integer oleaal bine dizo are| poole
Pido tbls eequives) Jo Find the seb of gobs serch thet
aU the ehosen gels Shoulel be completes} wrthio thei
deodines ane the pool earned! shelal be menimunm |
with the Fobleoing eonsfeamnds-
Oo only one mashne is avertote Fo pcs iegb |
Oonty ane gol must be poecesseal oF any pou
Example oblain -the optimal Salutin fio Hheqob Sequencing
pooblen vot deadbines whore = 4 (mumber at yobs),
pookils (A, Pa, P,P) = (100, 10,15, 27) arul aleacdhines
(Ai, ds,cts,dn) = (21,21)
Given
if: le ]3 [4
Sa)”
Pr | too] to | 1S [24
& Poli jer} sor cbpth
Arevenging theses in deenenurey vcler eh Pe
if; Jo ]3 [4
Pi Noo { 27 | ts lo
ayfols fe)
‘Scanned with CamScanner Se! geet & det, prety der
\ 2 yee
aft Job 5201)
ala _] poof = 100
SAepe Sdeub leo, Py =09 anal diz!
' 2 3 &
i| 211 | Tob J $9,1}
d}i fe | polit = 27-100 = 129.
optiinal selutinn = 20,19, B optimal poof 12-4
lohed ts the sobdin generated Gob Sequencing |
© pooblern voitty dead Lines Whey od, |
(Py, Poy) = (3,516, 18,1, 6,20) 4,
(dy da, dz) = (13-4, 3,2, 1, 2)
by)
gel? Gren ode oroengee) in deseroling order:
. T
ify jolsala ls lef ]/
Pil ao\oolie | 6 | 5 ]3])
ad} 2 14 \|3 \ a] i[
Step) Selec Tat, fre ao, dieo
ot T43
dpe pooled = (30)
2 Yeoh 12, P 290 djch
Ber Me gad ig
sh 2 T= 9123
a \ 2\4 Pooks} = 30420 =SD
4
Scanned with CamScanner J Sz $1,324
EEE pools) = Qoriorre +68
Seleek teh, p26 AAiel
4S
ioe
ale [| T= 3G,1,3,23
Es
3 | 41 I polit Gr Borle+20774
Gphncl Sobuhon ts { 4,1, 3,24
optimal) Nedue s = E+B0t18-+ 202 74
ee
‘Scanned with CamScanner @
BD obkary the optimal sedution feothe Job saquly
peoblen given he. FoVlecorra, gobs, poolilharal thers,
ded lines. 4
iia
2
2
3
3
&
4
4
Pe w \ 1s
\o
oS
a&joejols
Garren gob poolish iso cama cele
»
=
3
Ss
c
\
| 3 |
Step) Bele fo1, Pye 2o, be L
s 4
\
J\t
1 3 ou
Jeb= j= o9
Ajo |
pooke) = C20)
2 Sled f-2 PHI
ghee i
2 >
Eyot 7 I
4
, ded
s
F= 91,23
d
A fo
2
siep3 dle 1-3, pps to ane
|
prolid = 204 ( o235-
A= 1 tars gp B ne
Sdlectecl.
tos 3 4s
stvtay TT] eee
pio 2 | pool) = ROHS =35~
gah Suh Int tag dd
ale fal |} F-41243
a{ z{2[3L] pooktd-= 9.6 ris4+5
Spiro selutrvoy 21, 2,43
=40
oph > oj Velue Sho
Scanned with CamScanner inimar Cork Spanving ‘vees's fla]
A Spanning Joce ts adver 19 Wlreh all nodex
ORE Commested! vorthoed Peaminga closed pet oR
Cheeuth.
AL minimury Spanning daee ofa giro goaeh G
phaGts Sponning dove whose cost is minimuny
®
isa
awa vudk OU watires -
© Poim's Algsarthro
® kauskal's A\geartrn
Ereample 10
40
Bo
S20
Porm! Agency
626 M26
counkal’s Agandhon
e209 e~6
ao
9 ©. 9
© © © ® © ° cosh t
cost = 10 eto “
10 t
my} e » ° ®
80 %
Carn C Oq2
cost = 60 Gost = 60
Scanned with CamScanner @
‘poly Poi! s Algcarthn &, Kousled's Myeorthm
pr
©
F5 ® Io ro) lo @
6 @©@ @
6 o @ 2 ns
ws ©.
2 ow
cost = BF Cosh 57
lo @
10 ane IW \L6
© OF ®
w Ne IL
le 2h)
Pr
Coak= 9S Gab= 99
_ __ e
Scanned with CamScanner Ks usked's iN tee swith) porr
\v @ lo ©
6 © ® @
ID
© © d
() gst 20 Cosh = 2
O
to
o
| o F&F ®
G@abe we
iy I =74 ou
Cor> 99
‘Scanned with CamScanner ©
Excomeley Noply Perms & kauskedd Nlgye wether Pertte
FaUlowy goers
Ans 20s
Scanned with CamScanner WV al
% @®
f Singhe ~ Source, Shortest Poth Problem
ee
at
2
: 6
Xe Diyksdaas Alggatho pA
Delinidng The armgte goune elorferb pal peablen ts
tthe one whre to We compedle the shoaterk me
Prem a green gounce yeatex Vs to alt othe weathers
Tp the epeph.
© Boch He alerterk chistonee are shealest peth
From weoten. & to reader all.
Scanned with CamScanner _°
Fine)
S veV-3 div) =mso(A Wl Ale) +tntd) (ald
num}
5 0,1, 2,34 . 3,4
5S 0,1,%,4 . [dled = min (co, 4+) = 09 114
ALIJ=min (co, Gri) = :
lA£2] =min(co, Jp400) =c0
L4J= mines, 435) = 39
5,3,1 2.4 elf = 19 (c0, yr a=e 2,29
ll (27 = min (co, 14-418) =29
ol[4] =rin (Be, 14+20)=34
7 ..DhLU alfe} =min(ao,29+20) 249 | 34
alo) = m9 (34, 24-4) = 34
531,2,4
°
fo} = minfiyg, su+0)= u9 | 43
8,212.4
Alo} =49 Shajak dictence fron Ste 0 ts 49
ADs 14 Sheolead distance From G to tS 14
lo]: 29 wheat dutone Pom sto 9 Ts 99
dts} = 4 Shadab clisdene Prem Sta BIS 4
dla) =: 34 Sherk dutarc Prom Ste b 1s By
dls) = 9 Shatet dutare Fw Ste g 18 6
So
Scanned with CamScanner & ®
‘4 Solve the Pallawing single -socnre shea lst podb's pooblem
q ' with wales aas a 9 gouole
7%;
ve
A
Ss Ve VS AOI =min dws, dle] 191009] a, dlu)}
a b,¢,d,e 7 da il
aa bce — |dfeJ=emm(o,7+2)=9 |b,
dle = mol, Tr6)=12
dle) = min (0, FrO)=O
db | re | dfejemmnfia, argde re | Ol
ALe} = mio{eo, at oJ=”
abe | € Ate} =min[oo,12t6]=18 | & 18
lad. bee} -
Aa} =o Sheolest distor Prem cto a ws oO
d (b= 3 Shoetert obey dane Poor ab ber 9
dteJey Shatst dastane Prem ade ce ts to.
[]= 7 hats ctutente Prem ado cl 1s 4
(e) = 18 Shatel disdanse. Prem a 1g
Scanned with CamScanner Dijkstas Algeaithm ('n,w0,souere,d)
1 umber of yeadtees tothe apephe
1] Cogh colpacemy medaixe With yodne 6
WY d~ Shatob clujance. frm sousce do allather nodes «
&, lio tb MIdp
ALE) — ceab [oouree,, 1)
sino
enel bw
S8(sousee J4— |
Per lel wr) do
Find uavel dle) sucky het d (uJ tsmmrmur
ath a fo 8 ie, Stee
Ba evry ve V-8de (ie Reo v20 ce +1)
FC dfu] + roLu,vI @ &
be ®™ ©
&) (to)
SA
© ()
Shep
) (0)
@) Q@ > @ ()
© 06 © © & B
Scanned with CamScanner “) — pds
Coote, «heap (Top dbwni houp eich)
Tr dop down appara a heayp dan be onerd eo} by
Sunorsive inserdtay of a ned Key tnlo a paeviously
crended heap. The neo er Shouts! Be inseated alongs
aljor the Jost leak the exerting) heap.
Beomple Constouch a henp fea the dish
50, 25, 30, 4S, luo, 4, &e by auseorsive. Mer tion
uaina, ‘poo dwn appreashs,
Step) Peak Wen so inseales! Mo an emple doce
%,
4,
®
step% = ment Ver 90 mnscated rato heap
(@)
@)
Bee iJery 20 ingea ten! ko the hea
-
Set 95 3 &, Coes ard HEU gookathen
sort oven sect
; poge fe
‘Scanned with CamScanner hay
/* 5 = Tnavokeal_mto the heap
Ls maertesl iwi
a Bee
Sigh G 1 minal mo He hep
a
‘Scanned with CamScanner
— ~
* Constoueh & Heap fer 14,12, 9,8 % 10,18
% MO) 3 x Step
Ye 0 oes
@ é ©
S & Q ©
® © @®
Seo} 85, 15, 25°95, DU
Sort the Redleoiny dada to olescending order ustrg hap
Scanned with CamScanner — } en ev
greste a heap Paton -up heap Cnstructiv2)
Jo 5, 35,25 4s, 20,55, 25,45, 50, 10,3 'S
& 14,10, 9 8, 9, 10, 18 a
lor 2,3,8, 7,103
Broa vec. 18 confouctesl Feo the sf qi
sie!
bot am dorkey 10S
() ens ard ager gaoep
£ dod ®
© So 2%: eee
Se Lab us onnpett— phan ethan
eo arel \o 8 gee od q
‘keep a9 Sim
Lebua compare 12 ard 4
And iu is. guedteo tran ‘2,
Compose ly ard (8 @
. ” “Scanned with CamScanner Me 0%)
jeap Sart (Sooting Deine a heap ) ps
%, A-heap con be tesco] do Seah Phe number in
ascenting oRdescervliry coder. ths goo ine dechn qe
which uses harp do amange numbers 10 axerding |
descending ondler 3 calleo! heap Beak
Seadrng Phose} Py ples phowe. idems me onvongol
in asceneling order ce we Udt MO heap) op clescondiing
order (16 we ye mro heap). This Bs aobuerel by
gepentelly per Foom ig te ReLRoco ey aadpyitier- _
Exchange. cthe woo} dem do-[he. enel ob tHe heap
Example Heap Scot 100, 75, 80, 25, 5b, 20, 4S
~~ Scanned with CamScanner count S TIEN ee
see
o
Bxobo
1 ) Gah apy, of ofa) Oplimad “Toce Pooblens}
Hafan Trees and Codes : a
“This alyoorthne Ys bavieably a cocling Jechnique Aon
erecding dod Ruch an encoded deca is tured in deta
Comprerstery cleohmeyes.
® Ty Hulbman's coding method, dhe dota vs mnpeittes
Q> @ Sequence ct chersaclers. then q table of Prequency
et occurence of each cheaaeb or yo the doch 18 bey’ bt:
© frum the table P frequencies Hullmon's free ts
~ — Construyetea} .
The Hublmon's tree rs Further usee! Lo encoding,
each charadder ay thed- binoag eneeding ts obhas necl
fos given dota,
ExemBeQ) abjarry a Bet of optima) Hub Pian cade feothe
Mersages (1m,-- Mg) wort Velachine. Foeqquiencies
C4-~ 49) = (4,8,4,8, 10,12, 20), Dsap the decode
doee tea this ach of coder .
BE Gren dade ty arcendiny cocles :
Lalli Talefeb)
Comore (rusk sree ies are foun tte dibte. ave omahe—
]
EI
Remore. 4865 Fre the table anol rmyont9 at
appeopeinte posshep inde
‘Scanned with CamScanner
24 a5
Tale [3] 40 [2 fro]
Skepe Combine fitk to stems Pate the fabbe
“} (el
Remere. four & fem the table ard. inteat 15 ab
Appropriate. positicn
Shep? Combine Fert tegre bras He fable 9810
@ lol
tel Tel
Remere. 9 & 10 Foon “the “lable are tral 13
[12] t's | 13 2 |
se Combine choy entries V2 4157
|
“_e rol ungert or
|
“Scanned with CamScanner
Rernorc. 1e&
I
Eo a @
SHEE Conome 193 830 Fen ste table
)
\
@
2
)
)
>
)
Gl
Rene. 19 8 no Bran He table ard Wak 39
‘Scanned with CamScanner Ne
oe8 MoekOon bel ehile! anol | en Alght choutol
\o}
C1 L213) | [ie] a 00
° 2° ial
[a]
Erearmple Obtcuy a gob of optimed Hulfmas codes fer :
sthe. messages (1m, -- M6) wits eebolive Preerencied
(H-- Ie) = (2, 9, 5, 7,9, 13) Dow the degode
sree few this aot of cecley
Example @) @ heb rs tHe optt Ime) coche. es He Pablewtry
~setot Preaercis art but, C19, dia, e15, P58, 9:19, bi}
Sethe Arne daber
[as by [era {dia exs|fie 9:13 b-4]
Ses Comlare joe tems Rr tte dalle § consdoxel free
cdalode areal treet QD
indo He able
Scanned with CamScanner eC
io
abs)
2
BE Gomlme Fierk tas tens
(4)
%
a} fel
Remove 019 ave) 9 Prem the ‘table ore) mngeok 4
[aela ers [fis 9113 [bi]
See? Combine. drest tooo antares
[ers 1 [#8 113] bai]
ae Label
i
~~ Scanned. with CamScanner @
SkEF" Contane Dent deve enores £/8 ave
Scanned with CamScanner @-
SNPF Combine frert too entares ofthe table
Code
VAIO
THAN:
LLG
Htlo
WO
lo
10
8
Scanned with CamScanner Cram ple @®
Example tind an opdimel binary meage thee ( pattern)
Fo ten Ailey chore length ase 28 22,19,5,
8452,9)
BS, Band 1), also Pinal
W's wejg tea) catheancs) pally
re:
= 1G dada In arsencting orelar
®
ee
Remove. BR 5 Poem tole ard adel 8
[2 fe [oe[ea]25] 52] 4p)
sie
| Comboire East tor evtores.
©)
es ti
ZI IE
12.) yo 28 [9205 53] an [9)
sep
Combine 12 ard 19 Prem te tabde |
Scanned with CamScanner @®
Qi)
re]
@ ~
3] ts)
Remoe 12. ard 13 Prep fle efeabste Orel inwent 3)
[oat [ee [assole]
sit
Remare. 28 ancl &1 foun He Yable are)
Inet 59 30| 25 [62] es]aa]s)
Sips
Combing 42 are) 85° fam He sable.
Scanned with CamScanner 33
[3]
Remore 2 are) 35° a He +table orel adel 67
Tfea|ai
seb cone nari b
()
3)
a a J
ae] @
(18)
(s) In]
211
Remere S8are| 54 fran te table anol tneetyy
Scanned with CamScanner Q
SAPS Comoine 69 and 84) Pron He duble_
(s)
@ [84]
32] 13
Remar 67.324 fron He table arel inert 'S1
vats,
Set Combine St aro} 112. Povo He fable
Rernone. 91 Aro] 112. F200 He.
stalole ancl Inserak 903 tdo[2 |
the doble 1
=~ eT .
Scanned with CamScanner Shep t ©
SEEPS Combine. 151 anol 202 Peco He perb be
Elena) pest dengel =
File. beng * dastone Poanere }
Exdeanal pedh = (3%4)+G6 7) +(liox6) + (1295)
+ (28"4)-+(53%3)+ C91x0)4(823) |
*(95729)-+ (84 42’) |
= 1004
Freleana) Posty deat = loog |
Scanned with CamScanner Roe eebentetenatnd FV
Assignment 3 Sub! Aon(igesngy
© objeto the optimal gahdin Ly He keapscck
probten using greedy methool Geo the Pebocor
@ M= 40, 23 ua
‘d
gh ) =o, %, 10) §
1, Po, fa’) = (&o (80 40,25)
We %, y= B Wei
' BH (0, We, 8)= C18 16 49
Poh, P= (a0, a4, 18) 7
© Whed ts eb Seaquencing with deadline pooblem? find
—_ Genercdedl by qo Sequencing problewy with deadbing
F5ebs geo polls (3,690 18, 1,6,80) and deadline
(1,8,4,3,2,1,09 cvespechvely
lohad ts minimun Cerca oceg Apply Poim's §
kcrwkod aljeorthnn Pea the Pablo gephs.
Scanned with CamScanner ® sing greedy method base, the fedlowoiog graph to
get sherlea pedb Prom veorlen ‘a’ -terthe al) other veoh ex
© Whoh s heap Conslouh a heap Rothe Orb
60, 95, 30, 45, 100, 45 Bo
top dow appooech .
© woh rs heap 2089 Consort Hesup Gort feo the Dist
100) ¥5, 80,28 50, 30, &s
@ obsein a seh of opliinad Human code Rea the. messages
Cm, mz, -~my) wrth velodive. dequoneies (4 4-~ I =
Ms, 8, 10 12, 2/) Daw the decode thee foo-thrs
te We. Seb
® Consloud- a Rublman Sree one) Resetting code wood
fer the fete :
fren s\sfelol-]
\fookabili te [O35 | 0-1 [0.2 Joa lous |
by Stcebive insertion sing
Encode the weod DAP are ADD
Scanned with CamScanner Shanti Vardhak Education Society's
BHEEMANNA KHANDRE INSTITUTE OF TECHNOLOGY, BHALKI
Dept. of MCA
Class:3"' Semester 2"IA Test Max, Marks :30
Sub: DAA (I8MCA33) Max. Time : 1:00 Hr.
Note: Answer any Two full question,
QM A) Obtain the optimal solution forthe kna
the following M=40, n=3, weights
(Wi, Ws, Wr) = (20,25, 10) and profits (P (30, 40, 35)
Solve the following single source shortest path’s problems with vertex a as the 8
source.
ipsack problem using greedy method given 7
By
Q.2] A) Obtain the optimal solution for the job sequencing problem with deadlines where 7
P.
n= 7 Profits (P,P, (3, 5, 20, 18, 1, 6, 30) and deadlines (4), d,...d3) =
(1, 3,4, 3, 2, 1, 2) respectively.
\ B) Construct a Hluffinan tree and resulting code word for the following. 8
Character a; BT c Tp] -
Probability [0.35 [0.1 [ 0.2 | 02 [O13
Encode the word DAD and ADD.
Q.3] A) Solve the following TSP which is represented as directed graph and whose edge
lengths are given by cost adjacency matrix,
Q (2) 0 10 15 20
[<<] 50 9 0
LS 6 13 0 12
O—) 3-8 9 0
B) Obtain a optional binary search tree for following nodes (do, if, int, while) with 10
probabilities (0.1, 0.2, 0.4, 0.3)
OR
4] A) Apply Warshal’s algorithm to compute transitive closure for the graph shown §
below. @)
B) Apply the Dynamie Programming for I following instance ofthe knapsack 10
problem, Knapsack capacity is W=3
Item Weight Value
1 2 siz
2 1 S10
3 3 $20
4 2 Sis
Scanned with CamScanner
