0 ratings 0% found this document useful (0 votes) 12 views 38 pages Daa Unit - 3
The document discusses various optimization techniques, primarily focusing on dynamic programming and its comparison with greedy methods and divide and conquer strategies. It explains the principles of dynamic programming, including the principle of optimality, and provides examples of optimal binary search trees and knapsack problems. The document emphasizes the efficiency of dynamic programming in solving complex problems by considering all possible sequences and avoiding redundant computations.
AI-enhanced title and description
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 UNIT - 3 For Later a St Martins égguneris avese- Mt Material
Syllabus
= General Method
~ Applications
optimal binary Search 1ees
— 0/4 Knapsack problem
All pairs shortest path problem
~ Travelling Sales pason problem
b ~ Reliability Destgr
General Method
Dynantic Programming ‘6 typically applied to
optimization problems - For a given Psoblem Me may get ony
of Splatters - prom alt those solutions We Seeks for the. optimum ,
‘ ue Solution). And Such
numba
Solution Crfintmum Value or maximum val
an. optimal; soleetfon. becomes the Solution tothe
given. problem
method
EE
Diflerence belocen Dyooonte Regroriting b Gieedy
Qynamie programming, Gueedy method
vs Gxscedy meld tgpatthon
bs,
$5 alt osed sor cbtatatng
eptimam. Selarion.¢
+ Dynaettc’| programing -algextth
used'for obtaining opfimom golertion .
2. Dynamic Programming “considers 2. The greedy method 14 @
all posible Sequencét Yn order cbtain —slaatight -foricaad methed for
cthe optimum Solution i Choosing “the. optimum choice
' i oF Solution. Lt simply Picks
Up-the optimum Solut’on 10tthout
. tevising -the previous Solutions .
F Dynamic Prog taming Uses Botlomup 3. The Greely method “Wxes.
roach 49 oblain he inal Solertion top clown ‘appioach to dba a
the nal Sokelfon
™ rf
Be annxandeed that owl! qeneiate i RRA cee eddie DeSemiAnAe taiythablly Sotoge MM Material,
1 in divide and conquer algestthm
We fake the problem and divide tt
‘into small sob problems these
Sub problems are then. Solved
findependentty - And finally al the
Solutfons of Sob-problems are
collected togetho. to. get the Solation
forthe given Preblem - These b-
Problems ave Solved Jade pendently
without Considesing the common
Sob
&. Divide and conquer ts Recliisiuely define the value of an_ optimal Solution . —_—
> SiMartins.toginaerig Colege-8M Material.
por thet gout have to develop a recurvence relation that velaks a
Solution 4o ik Sebsolertion Using the mathematfcal notation of
Step 4.
compute an optimal Sletten from computed information
ulrciole of optimality
the dynamic. Programnting algoiitim obtains the Solutfon
Using principle optimality.
“the principle of optimality Stafesthat “in an optimal
Sequence of decisions or chdices » Cach Sobsequente must alto be
optimal”
Hhen at %& not possible to apply ‘the principle of optimality
itt almost ‘imposible to cbfain ~the solution using “the
dynamic programming approach -
‘or example : Finding of Shortest path ina qiver geoph uses the
Principle ef optimality. =o St.Martins Enginnerig College - MM Material
OBST (optimal Binary Search twee)
Suppoge Ne are Seaxclting
for “hat reqettied ord we have -to look up diconary - Bak
this look up cpaation is move tHme consuming process. To
avoid this problem, We can build ost. Sn this frequently
Seaching Nords axe nearer to the woot and less frequently
Searching words ase awoy from ‘the soot- Sucha binasy
Search tree maner cur task moie Simplified as well “as
cHtictent- “ths type of ey search tute $4 also Called
“optimal fnavey Seasch tee > * (ssi).
let fa, a, -- = any bea set oh identifiers Soch
sthad aicar< ~-- an tet PCi) be the probability of Searching %
(on Successful Search of M%.
qi) bethe probability of Seaachiay, element X
a Head fom dictionary, Stdlaninspsinneri i
RoiRerGp clege MMaterial +:
method, Me Can perform folowing SHEPS -
Nap = Mts HPP eT}
Cy = min i ee
ick 3
Ab Cig =0 and tp eat Hy ae
Goz® Cn =O Gq, =D Gs *P Gq =?
To =o TU=0 «G20 gO Mele =O
Sintlasty ere mia f Cj rer Haj tht }
icky
Let feo fel so, o G73 * nin | en $43 +N}
= 04849 =)
Cy ate
v3 =2
Sov k=3 Cy = MALS Ss tos}
= 44049
Cig = lb
Yar 3
fiom. the above two sSolutfons Le will Select wi dimum
valeur of ¢)3 15 12+ That means =a giver “th minimum volute
me
le feQ f=y 2 ES OS Be Nee
Algorithm. OBST CPi 4, Ws Cr¥)
for i: =0 to n do
Chis =07
wULidieo
ahaa s> MUG Kaye RIM
Ci = Cika t Kj thy
vay =i
4
for mi=24ondo
for jo 4o n-m de
t
i¢my
Kt
min value CC,7/ 1,5 )}
Clg): = MLD IT Heth we HOUR,
WijT tek
Eh
4
tavtte CCLosA) ¥ Coen) J. iS thyiMeHg College - MM Material
Algorithm. Min -value Con ij)
z
minimum =
for Case s[tg- to rit .fi)do
1
ff CcCt, mt] +¢0m,f]) < minimum then
minimums = ¢Cimajeclmj)t
Kiem!
J
Yetun Kk}
f
ro Ear Gealing dice
Algnithm butid- tree (0a,1,j)
I
Ti = newCnode) ;
REE NRG
T > data: - alk;
T> left = build— téee (1,0, 1, K-)"
To vight = bald -tree (1,a,K J);
Example: S Using algortthn. OBST , compute Att, sy £ Cay tor
Identiti set {,ar, 45, ay} = fond, qoie, prfat, Stop} with
Plate} = {tbo j 15; ‘ho ,tno} 9 fo=u]= 454i, "5, 20, ho}
sd: The table for WI Can be sepresented a5
Woo=ts| Mn = tho | tay =%5| Has = J ae
Hot = ag] Mia Ha | Aas = oof =
1a ig a
Ups = Is]. St.MariinsénginnerigColege- MM Material.
4,748, $4) -ton% = 4s. 43 2tho, 4" Ihe
= let rot ho = td = ho
0
fet for
pblalai = HAS = Sie =
aoe To
Ay = My + P3445
xt + 4,
st+tek loo
Nay = Naat Pa # Ty
ect th =o
joo jae
Her = Nort Pet he
= Je: SHEP ol
Zttte a bo
' 20
I ferge3 2
Uys = ly t Pst 45
for2t) = 13h,
2& a eet bo
egtbtt Zo
tea fey
He = Wha tp A tg
2 bea Fag MY
= |
eBbrs iho
. feo ges
ly, = Ay, + Pat 43
oe tolerate = 18
ebrhty
i
20, tr St.Martinsnginnerig College - MM Material
Nig = Wis + Py t Fy
= IB oe hd os 1S
ao tate “20
tzo f=4
Kloy = Noat Py ty
oft of ASE Ue
gtaotz = ™ho
Computing jr values
Coo=o | Cy=0 | G,=0 C5370 Cyyleo
TorO | TO | Gae0 | aso | rey co
Goi ="lao] Sin =Bhr0 | C23 = fon) Cag = Fu
tye i
NED | Hee" togee met
fs)
or =Abd Crs ¢ y= Yh
Yor= 2] %32 2 rasa
232 | Cy = 24
Cos = BE | Crq = 24
teense
oy =
Sire ee { Ci + Cag thy
tet feo, fel ° o taofeq ket
OBsT With minimum lest Vets ‘220
¢, |
StMastins Egiinerigeoligga. MM Material: , 22]
Qe Var bei» Prey, Pom lB , P3=PH= NG 7
(a) construct “the optimal Binary Seaych ee. a8 a minima) cost tree.
tb constsuct the tables of Values Nig, Ci, Vij Computed by the
aloxithm 40 compute cthe wots of optimal Sobtyces
Sl The table we an be vepresented as
Tetse= | e= 3]
Meri e |
Hers y [Naf | Ka“Ahe| see]
Hor Pig Ma= Shy |Moy= She
|
weg = Mega 4; HY :
| let jzo f= tet f=3 fey
| Ug, = Hoot Pit Ti aa the tatty
j Sota es mkt th
a)
o+ at ha 2
Te mio ht
by ed let feo feu
sel Upp = Hoy + Pate
eet, fee bey
Ua = Hat Pete iets te +StMartins Enginnerig College-- MAEMaterial
Wy =
ag = ba + Pat by Whey = Brat Pa thy
Aung le .
ie tw th et TE
by 2 by 219
tet feo f23
Vox = Wor #Ps tha
= Jo ep ded
et ett wet ti
Rog = pg, = Lee
ty = Fe
computing Oy and Vip values
eo
Vp = 0
Coy = the [Cin = 616 |r, =3hte! Cae = Fhe
hoe t |= 2 |vaze 3 | Seeep
Co2= We [Cis = [ey 8116
Voz wl] Yiat > |e 23 J
Coa AUIG] Cee= lie
wos? 1 | Y= Qa
ke,
—
cy = min ) Chest + eee + if}
-O2KST
let feo j=l ocleg! So, Kel
Cor = Coot Cy toy
= o+ot
Co =i
Yor =I
tee fat fer
Cn = ent Sy tN
lekgo, So, Kee
= 04046
1
aks So, Ke3
we. Dies Startins Enginnerig College - MM Material
Cy = Gs t%y? Psy
= of0t3
Te
Gu HH
tel feo Jor O OF wea 9
ox a bag fn chich “the object 1 that hos
pacity KI. Then “the pit that
“the objective 14 to obtain filling of
fver. n objecld and a knapsack
Metght Wi 15 40 be
placed. ~the knapSacls har a cay
can be earned 1s PIX}
knapsact with maximam. profit earned «
1 l
maximiged I PIX] Subject to Constraint i Li xt Nk ythen. Cp;,Wj) Can be eliminated .
this paging dule ts also called as “domminance'sule. Sn purg'a)
aule basically the dominated ‘eples gels purged. Jin Short ,
yemove the Paiv With les profit and move Merqht-
_Ex! consider knapsack instance M=8, and n=y - tet Pj and Wi
are a& Shown below-
i | pry
{ tfo
x £ 3
3 4
G16 s
pF A pe iydla ne aedlenceog dectaton, S18, S)% st
ste { to, 05
Si = { select next patr of (p,nyb add fr 7th sy
e fey
si 2 {meege 32 Sf
= 4 C00), C2)
gl {select next pair Cpyis) and add te oith $f
efi), 2.53}
ge? = {mage sit si}
= 160) C2, C13), 3,5)}
gt 2 {select neck pay pus) and add Ht with s*f
= {6.4),C6.6), C0, BAI}
8 - [Mage sesh}
= (0,0), CHO), (23), 03,5), C54), C6), CHD,
(8,4) 5 St.Martins Enginnerig Cotleye’ Min Material °°
aasome (Pz, 195) = (3/5) and ( Py, WK) = (5,4) ~ Here Pi < PK and
My>Wyg 1 true hence ve wil eliminate Paty (pp, ) near)
from <.
se] 6.5), G4), 6.9), tn, 9), C12.) C812), DY
gts { 0) £429, (2139 5:99, 610), 49, 6D
(615), 8/8), Ca) C12), C131 1, cy a) F
64 contains all porsible Solutions 0} (P.49) Pairs «
Now, Ne will conbider the Knapsack capacity w=8-
So, Me can Select pair (8,9), it tata sth.
go, consider 47 object (pj Wi) = (6,5)
vyemaining Wetght = (8-6, 8-§)
hey (a3) = TE KT 24 object
pats (2139 ES Hence arabjerk is Q9
‘vemaiining wei ght = (2-2, 3*3)
hes) (0,0) Se, ro wait remaining -
So, We get the final Solution a4 f 0,1, 0, 4
ER consider the knapsack for the Gnatance N=Y~ (091, We, '3,9q)
F105, 6.9 and [ Pi, Px,P3, Pay = 1215/8. 1} and m=2l
sa st =e Mi} 2
ee {eo} lef = {en0j Bg
paki
!
g' = {metge ses}
oF
10
= 40,0), 2105 a
hoe 46,15), (7, 25)4
eh = 4 toon, (2,10), C5115), Cs 25)5
si = {84 (1o,u) , (13,28), 15.304
gb = f toy C20), C5715), C86), (10,16), (13.217,
: us.)
a . $n), 3,9), C620), CUI), CH, 25), O43), = SkMajtine Enginnerig Coed “Mm Material ”,
14,30) C16 40.
(3119), C6124), C4015) (1,25), C
| Now, 34 contains all poastble Solutions of (Pit) Paies «
Pair (4,25) 1s eliminated from S* becaue of purging ae
Now, We WIT consider-the Knapsacn capacity W= 2!
Go, we will select paty (13,21)
(2, Wess.
F Hence set 3 %5 (8,6)
ss remaining wetght = (3-81 ai-b)
SiS Ss”
Hence set 2 14 (6115)
yemaintng weight = (6-8, 1s-15)
= 6,0 So, no weight vematatag.
So, We get th final Selection as { eh Ten
EX'S Salve the following OBA knapsack problem wsing dynamic
Progamming {01 )P2, Ps, Py} = ZM2t, 31,93}, Leo wes Ws, Buds
22,11, 2015) y mayo, n=y-
* Given dato
4 | pt fut
fae
2 {a {a
3 [ 8) [22
y [33 [te
so2 1,0}
se fw ay
sh = {60,0925
si = form, 32,9}
sre | €0,0),C12), 21) 2 ra}
gh 4 (31,22), Clr2 ay) 152,93), (63, 959}
2 J coye),C1,2) Cat), C3213),C31 122) C24)
(52, 33), (63, 35) }
3
SP = | 033,15), C0 (17) C54, 26), 065,28) , (64 317, (15,3, St.Martins énginnerig College” MM Material” °*”
(G3, 35), (33,15) 3 Cute FI), C54, 26), C65, 28), (60,32
(45,39) (85/48), C16, 50) F &
consides. knapsack weight m= lo
We will seaach for afaple fa which value of uo
Thee TA no tap having 48, $0, Ve Whtlaneay by value
toe will Select (95/30).€84
ath object is( Pi Wi) = (93.18)
Femaining weight = (35-33, 37-15)
2 (aajes?.
So,
Fobject b > 31,22)
aremaining weight = Caq2-al, 24-22)
sinttiiray esl,
OP object fA C12)
= Cite, 2-2)
= (0,0) $0, no YeMatiafaeg wvelgh
So, we get the final Solution as J 40,245
yernaining weFght
cee mat, 28, omiiey tind = Lip beSbon Lape Pte 19h
Givin data.
1 | Pi fW?
wt
2 2 ls |
3| 4
sh = {com}
gy = Loy}
ahs {toi e129}
st 2 | ¢13),¢3,5)}
SPs | C010),C12) £23) (35)}
7 gto 1 t,39/€515), C66) ,C418)$
Sf Cop0), CH2),C23) , 5), 4138), 088), Og
(3,8)}
Here 6,5) fs eliminated Using purging vale - SL Martins Enigtire fi 4 ‘
i fte will Search for & tup teak ‘Wu Material
" So, we will Select (6,6) es.
314 object is 60.3)
remaining wetght = (6-4, 6-3)
= (23) |
(a3)es*
ond objet 4a (2,3)
Yemaining weight = (.22,3-3)
= (0.0) Ao sematining coetght -
$0, We get He final solution a Jo, 4,4}
Ll Bass heat path ste
Soppose if given graph i Weighted Graph -
Then objective {5 4o ind Shortest path bdiacen each and every
Paiy of node present fa given graph. :
To find Shortat path between. every pate
Of nodes Using dynamic prayramming , We need to find AG
‘for Keo ton. Ay represent path behucen iH) via
WeWlLGy
K . kt ka Kt
ae min | Ag ATC FAK
"consider given graph dnd -find shortest path between every
Paty of nodes using dynamic Programming.
Ae= Wl
t az q
aoe Ifo gi
‘[: o 2
alsa 0 |
Alas min {Aks LMat ais} wo
2 ef i Sat etal
Ag = Te fay Abt Alo}
te. Ss = min {3,488} =3
3 ' o & &
A a Sa t 4 4 4e
2 {S20 2 Ap min} Ay, Aist Ai
B ys, at. = mio la, ee} ©
3 e e
4p = aio | ab, Maat 5)
smin | 8, 243} = 5
AP gives Shostext distance beboeen any Paty of vetices-
i,
av «
in
4
°
t2ay
' 1 2
abort & So) sala tind tel dh ee
4 ' a
: Sau S Aga 2 Lady Ait righ “eat
Aan Why tart ed eed =
Ag Wh ter thd HH
A, Mad BAS
ays= fig teas tis} deeds ip College, MM Material .,,...
=Afeey 8)
Alada) Kent}
eee
Aly = doy,
Hig 14h, Art Mes
Ae = 1m, ata d 44 we
—— = 5 ata)
Lys at Mah fae}
bes y
3 1 fo o ¢ eH. Gif
nerfe z s fie cnt oe eo
B pee e 6
lets ebay, Ma ta) EY
7 Ear f= (te, 844
‘ a Aist 85y } (te, ae
; oly Mat Ms iat af * (GiB) & S
a * =(n, 5#4)
Ae tea* at ™ ide, ay 3
i, “bh tier «eee
at = Car te. 1644}
Ye de, Aly +a} = ey
id a, Aye Mer} + ir
Ags Jo3s, a3yt ys} = {5,243}
=5
Wa fats ate
me
Ai {Ae Sle ete Lapa
= jm, 145}
Ait) * = fr, But Ht
i Starting fupinnerig-@ollege> MM Btaterteet=-*)
(S) matiix graph vsing Floyd algorithm - ae
tr 3 qs
! oan! 8
: a ett 2 ee
At > G0 Yk
y ~ 46 2 05
s[a ee %%
& z (21s. Fa
eo yey = (3,666) 73
ae ives! 2 A ta Set) 0
24e0 3 208 aang pecan)
3/44 04 © As {Ag, Ds
G Pow Ve S bal a
sl(s © « #0 Oat tea ee
= ie Aly i ; athe aaiaal
° 6, 64854
es ditties f
5
\ a, fa to Aid if
N =
Ags =
of a (xs tb )o+
fs -{A55, A etist =f i)
Gh BFL )EE
Ag «ffs agit his} *S a
Ais
Alyy = Mow, ay ty = & 3H) of
: 5
t. a3] as filalntda = eh)°
wee a eo aGir 8 asl} = bea, eotb)2%
2/603 2
“ar lies ob? IES.
7 1 Al gal alee etbyae
el ects” Bh at YB Bo Met, Meat At (#48)
gloat Be | ue
wet a
= Sit 'F
Tals, alas alg} = Ce 15#3) 8 we 2 AY.
eur
moon 3
ng Enginnerig College - MM Materiat: *
60 3 A8 wpe
44 06 be
ats 4 2 1, Ait Ab pe @- aed
Boe Be, Pe
7 a
Aer
Wag? lee , 2¢4)
Mat Pra, nists} en
. =u
a de re Meg t Ais} eilaae
Ass =
Maar
GS
2 2 @ 5s Reg tay Mtg) Me a+)
ag #
A ey 23
6.6 3 im Al, ={Ae, Ay 1% om : is
ik
he i : ' a4) =f, by =Geues)"*
3 FL ee he fad, at Mad = ©
a
Abs [nag May t a RGus
“gc el) ey,
fat ad galt, | CG 7t8
E fal asa} ( ; io
ae sy ai stn} ea
ae -fat a
feat fab, Abs? ab} We, 1
eet
paitoor? Ascal
lw what aie the differences between Divide and conquer and
Dynamic, Progyamming .
k :
Uy What are the differences between greedy method , dynamic
Programming approach -
(3) Give the commonly osed designing steps for dynamic programm
algorithm. :
F tq Uthat ts princtple of optimality ' Explain wtih some, Suitable
example? i ;
U) consider “the Knapsack ‘instance | Hl
G,4,2,3) and ber ghts w
tth & Objects and a capacity
Mell, profits p= (5 = (4,316,242)
Solve ik Using dgnamic programming ap proach
inary Search algorithm with “the help of
) Explain optimal. bi
Wap discuss “the time complexity of
Some Suttable example.
gee algorthin .
ules in O[4 knapsack problem. 87
shortest Path Explain With a~ gm
example .
(D Detine merging and purging q
(8 iytte an. algorithm for all pairs
