Modul

e-4:Dy
nami
cPr
ogr
ammi
ng

Cont
ent
s

1.Intr
oduct i
ont oDy namic Opti
mal Bi
narySearchTrees
Programmi ng 5.Knapsackproblem
Gener almet hodwi t
hExampl
es 6.Bell
man-FordAlgori
thm
Mul t
istageGr aphs 7.Travel
l
ingSalesPersonprobl
em
2.Transitiv
eCl osure: 8.Reli
abi
li
tydesign
War shall’
sAl gori
thm,
3.AllPairsShor testPaths:
Floyd'sAlgor i
thm,
4.

DeptofCSE,
CBI
T Page1
 DAA-
18CS42—MODULE-
4 2020

1.
Int
roduct
iont
oDy
nami
cPr
ogr
ammi
ng
Dynamic programmi ng isat echni
que forsol vi
ng pr obl
ems wi t
h ov erl
apping
subprobl
ems.Ty pically
,thesesubpr oblemsarisefrom ar ecur
rencerelati
ngagi ven
probl
em’ssolutiont osol uti
onsofi tssmal l
ersubprobl ems.Rathert hansolving
overl
appi
ngsubpr oblemsagai nandagai n,dynami cprogrammi ngsuggestssolving
eachofthesmal lersubpr oblemsonl yonceandr ecor
dingt heresul
tsinat abl
efrom
whichasoluti
ont ot heori
gi nalprobl
em canthenbeobt ained.[
From T1]
TheDynamicprogr
ammi ngcanalsobeusedwhent hesolut
iont
oaprobl
em canbe
vi
ewedastheresul
tofsequenceofdeci
sions.[Fr
om T2]
.Herear
esomeexamples.

Exampl
e

Exampl
e

Exampl
e

Exampl
e4

DeptofCSE,
CBI
TPage2
 DAA-
18CS42—MODULE-
4 2020

DeptofCSE,
CBI
TPage3
 DAA-
18CS42—MODULE-
4 2020

1.
2Mul
ti
stageGr
aphs

DeptofCSE,
CBI
TPage4
 DAA-
18CS42—MODULE-
4 2020

Fi
gur
e:Fi
vest
agegr
aph

DeptofCSE,
CBI
TPage5
 DAA-
18CS42—MODULE-
4 2020

DeptofCSE,
CBI
TPage6
 DAA-
18CS42—MODULE-
4 2020

Backwar
dAppr
oach

DeptofCSE,
CBI
TPage7
 DAA-
18CS42—MODULE-
4 2020

2.
Transi
ti
veCl
osur
eusi
ngWar
shal
l’
sAl
gor
it
hm,
Defi
nit
ion: Thet r
ansit
iveclosureofadi rect
edgraphwit
hnv er
ti
cescanbedef
inedasthen
t
h t
h
×nbool eanmat ri
xT={ t
j}
i ,inwhicht heelementint
hei rowandthej col
umni s1
t
h
i
fthereexi stsanont ri
vialpath(i.
e. ,di
rectedpat
hofaposi t
ivel
engt
h)fr
om thei
th ij
ver
textot hej vert
ex;otherwise,
t i
s0.
Exampl
e:Anexampl
eofadi
graph,
itsadj
acencymat
ri
x,andi
tst
ransi
ti
vecl
osur
eis
gi
venbel
ow.

(
a)Di
graph. (
b)I
tsadj
acencymat
ri
x. (
c)I
tst
ransi
ti
vecl
osur
e.

Wecangener atethet r
ansi
tiv eclosureofadi graphwit
hthehelpofdept hfi
rstsearch
th
orbreadt
h-f
irstsearch.Performi ngeithertrav
ersalst
arti
ngatthei v er
texgi v
esthe
i
nformati
onaboutt hev er
ti
cesr eachablefrom itandhencethecolumnst hatcontain
t
h
1’sinthei r ow oft hetransitiveclosure.Thus,doingsuchat raver
salf orevery
vert
exasast art
ingpointyi
el dst hetr
ansiti
veclosurei
nitsenti
ret
y.
Si
ncet hi
smet hodtr
aversesthesamedigraphsev er
alti
mes,wecanuseabet t
er
al
gori
thm call
edWarshal
l’sal
gori
thm.Warshal
l’
salgori
thm const
ruct
sthet
ransi
ti
ve
cl
osur
et hroughaser
iesofn×nbool eanmatri
ces:

Eachoft
hesemat
ri
cespr
ovi
descer
tai
ninf
ormat
ionaboutdi
rect
edpat
hsi
nthe
t
h t
h
xR(k)(
(k)
di
graph.Speci
fi
cal
l
y,t
heel
ementr int
hei r
owandj col
umnofmat
ri i,j=1,
2,
...,
n,k i
j
=0,1,...,n)i
sequalto1ifandonl
yifther
eexist
sadirect
edpathofaposit
ive
t
h t
h
l
engt
hf r
om thei vert
extothej vert
exwi theachi
ntermedi
atever
tex,i
fany,
number
ednothi
ghert
hank.
Thus,theser iesst ar
tswithR(0),whichdoesnotal low anyi nt
ermedi at
ev erti
cesinits
paths;
hence,R(0) i
snot hingotherthant headjacencymat ri
xoft hedi aph.R(1) cont
gr ains
the
i
nformati
onaboutpat hsthatcanuset hefir
stver
texasintermediate.Thel astmatri
x
(n)
i
nt heser i
es,R ,r efl
ectspathst hatcanuseal lnv er
t i
cesoft hedi gr
aphas
i
ntermediateandhencei snothingotherthanthedigr
aph’stransit
iveclosure.
Thismeansthatther
eexi
stsapathf
rom t
heit
hver
texv
itot
hej
thv
ert
exv
jwi
theach
i
ntermedi
atevert
exnumberednothi
ghert
hank:

DeptofCSE,
CBI
TPage8
 DAA-
18CS42—MODULE-
4 2020

v
i,al
i
stofi
nter
medi
atev
ert
iceseachnumber
ednothi
ghert
hank,
vj.

-
--(
*)Twosi
tuat
ionsr
egar
dingt
hispat
har
epossi
ble.

1.I
nthef
ir
st,
thel
i
stofi
tsi
nter
medi
atev
ert
icesdoesnotcont
ai hekthv
nt ert
ex.
Thent
hispat
hfr
om v
itov
jhasi
nter
medi
atev
ert
icesnumber
ednothi
ghe
i
jrt
han
(k–1)
k−1.i
.e.r =1
2.Thesecondpossi
bil
it
yisthatpat
h( *
)doescont
ainthekthv
ert
exv
kamongt
he
i
nter
mediatever
ti
ces.Thenpath(*)canber
ewri
ttenas;
v
i,v
ert
icesnumber
ed≤k−1,
vk,
ver
ti
cesnumber
ed≤k−1,
vj.
(k–1) (k–1)
i
.er =1andr =1
i
k kj

Thus,
wehavet
hefol
lowi
ngf or
mul
aforgener
ati
ngt
heel
ement
sofmat
rxR(k)f
i rom
(
k−1)
theel
ement
sofmatr
ixR

TheWar
shal
l
’sal
gor
it
hm wor
ksbasedont
heabov
efor
mul
a.

Asanexampl
e,theappl
i
cat
ionofWar
shal
l
’sal
gor
it
hm t
othedi
graphi
sshownbel
ow.
New1’
sareinbold.

DeptofCSE,
CBI
TPage9
 DAA-
18CS42—MODULE-
4 2020

moder
ncomput
er

Analysi
s
It
stimeef f
ici
encyi
sΘ(n3)
.Wecanmaket heal
gori
thm tor
un
fast
erbyt r
eati
ngmatr
ixrows
asbitstr
ingsandemploythebi
twi
seoroperat
ionavai
l
ableinmost
l
anguages.

DeptofCSE,
CBI
TPage10
 DAA-
18CS42—MODULE-
4 2020

Spaceeff
ici
ency
:Al
thoughsepar
atematricesf
orr
ecor
dingi
nter
medi
ater
esul
tsoft
he
al
gori
thm ar
eused,
thatcanbeavoided.

3.
AllPai
rsShor
testPat
hsusi
ngFl
oyd'
sAl
gor
it
hm,
Problem defi
nit
ion:Giv
enawei ght
edconnectedgraph(undir
ectedordir
ected)
,the
al
l-pair
sshortestpathsprobl
em askstofindthedist
ances—i.
e.,t
helengt
hsoft he
shortestpat
hs-f r
om eachver
textoal
lotherver
ti
ces.
Appl
icati
ons:Soluti
on tot hi
s pr
oblem finds appl
icat
ions in communi cati
ons,
tr
ansport
ati
onnetworks,andoper
ati
onsresearch.Amongr ecentappl
icat
ionsoft he
al
l-
pair
sshortest
-pathprobl
em ispre-
comput i
ngdist
ancesf ormot i
onpl anni
ngi n
computergames.
Westor
ethelengthsofshortestpat
hsi nannxnmat ri
xDcal
ledthedist
ancematri
x:
t
h t
h
t
heelementdiji
nthei r owandt hej columnofthismat
ri
xi ndi
cat
esthelengt
hof
th t
h
t
heshort
estpathfrom thei vert
extot hej v
ert
ex.

(
a)Di
graph. (
b)I
tswei
ghtmat
ri
x. (
c)I
tsdi
stancemat
ri
x
Wecangenerat
et hedist
ancemat
ri
xwithanalgor
it
hm t
hati
sver
ysi
mil
art
o
War
shal
l’
salgori
thm.Itiscal
l
edFl
oyd’
salgor
it
hm.
Floyd’
salgor
it
hm comput
est
hedistancemat
ri
xofawei
ght
edgr
aphwi
thnv
ert
ices
throughaseri
esofn×nmatr
ices:

t
h t
h
xD(k)(
(
k)
Theel
ementd
ji
i nt
hei r
owandt
hej col
umnofmat
ri i,j
=1,
2,...,
n, k=0,
1,
t
h
...,n)i
sequalt
othelengt
hoftheshor
testpat
hamongallpathsfr
om thei ver
tex
t
h
tothej ver
texwi
theachint
ermedi
atever
tex,i
fany
,numberednothighert
hank.
Asi
nWarshal
l’
salgor
it
hm, wecancomput
eal
ltheel
ement
sofeachmat
rxD(k)f
i rom
(
k−1)
i
tsi
mmediat
epredecessorD

fd(i
k)
I j=1,
theni
tmeanst
hatt
her
eisapat
h;

v
i,al
i
stofi
nter
medi
atev
ert
iceseachnumber
ednothi
ghert
hank,
vj.
Wecanpart
iti
onall
suchpat
hsintot
wodisj
ointsubset
s:t
hoset hekth
hatdonotuset
ver
texv
kasinter
mediat
eandthoset
hatdo.
i
.Si
ncet
hepat
hsoft
hef
ir
stsubsethav
ethei
rint
ermedi
atev
ert
icesnumber
ed
nothi
ghert
hank−1,
theshor
testoft
hem i
s,bydef
ini
ti
onofourmat
r
i
ji
ces,
of

DeptofCSE,
CBI
TPage11
 DAA-
18CS42—MODULE-
4 2020

l hd(k–1)
engt
i
i
.Inthesecondsubsett
hepat
hsareofthef
orm
v
i,v
ert
icesnumbered≤k−1,v
k,ver
ti
cesnumber
ed≤k−1,
vj.

Thesi
tuati
onisdepi
ctedsymbol
ical
lyi
nFi
gure,
whi
ch
showstheunderl
yi
ngideaofFl
oyd’sal
gor
it
hm.

Takingint
oaccountthel
engt
hsoft
heshor
testpat
hsi
nbot
hsubset
sleadst
othe
fol
lowingrecur
rence:

Anal
ysi
s:I
tst
imeef
fi
ciencyi n3)
sΘ( ,si
mil
art
othewar
shal
l
’sal
gor
it
hm.

DeptofCSE,
CBI
TPage12
 DAA-
18CS42—MODULE-
4 2020

Appl
i
cat
ionofFl
oyd’
sal
gor
it
hm t
othedi
graphi
sshownbel
ow.Updat
edel
ement
s
ar
eshowninbol
d.

4.
Opt
imalBi
nar
ySear
chTr
ees
A bi
narysear
chtreeisoneoft hemosti mport
antdatast ruct
uresincomput
er
sci
ence.Oneofitspri
nci
palappli
cati
onsistoi mplementadi cti
onar
y,asetof
el
ementswit
htheoper
ati
onsofsearchi
ng,
inser
ti
on,anddelet
ion.
Ifprobabil
i
tiesofsearchingforel
ementsofasetareknowne.g.
,from accumulat
eddat
a
aboutpastsear chesitisnat
uralt
oposeaquestionaboutanopti
mal binar
ysearch
treeforwhichtheav eragenumberofcompari
sonsinasearchisthesmal l
est
possible.
Asanexampl e,consi
derfourkey sA,B,C,and
Dt obesearchedforwithprobabil
it
ies0.
1, 0.2,
0.4,and0.3,respect
ivel
y.Thef i
guredepicts
twooutof
14 possi
ble binar
y search trees cont
aining
thesekey
s.

DeptofCSE,
CBI
TPage13
 DAA-
18CS42—MODULE-
4 2020

Theaver
agenumberofcompar i
sonsi
nasuccessf ul
sear
chinthefi
rstoft
heset
reesi
s
0.
1*
1+0.2*2+0. 4*3+0. 3*4=2. 9,
andforthesecondoneiti
s0.1*2+0. 2*1+0.4*2+
0.
3*3=2. 1.Nei
theroft
heset
wot r
eesi
s,infact
,opti
mal.
Forourt i
nyexampl e,wecouldfindt
heopti
malt r
eebygenerati
ngal l14binary
search t
rees withthese key
s.As a gener
alalgori
thm,thi
s exhausti
ve-
search
approachisunreal
ist
ic:t
hetot
alnumberofbi
nar
ysearchtr
eeswithnkey sisequal
tothenthCatal
annumber ,

whichgrowst oinf
init
yasf astas4n/
n1.5Soleta1,
...,anbedistinctkeysorder
edfrom thesmallesttothelargestandlet
p1, ...,
pnbetheprobabil
iti
esofsearchingforthem.LetC(i
, j
)bet hesmal l
est
av eragenumberofcompar i
sonsmadei nasuccessfulsearchinabi narysearcht
ree
j
Timadeupofkey sai,..,aj,wherei
,jaresomei nt
egerindi
ces,1≤i ≤j ≤n.
Followi ngthecl assicdynamicprogrammingappr oach,wewi l
lf i
ndv al
uesofC( i
,j)
foral lsmallerinstancesoftheprobl
em, al
thoughwear einterestedj ustinC( 1,n)
.To
derivear ecurrenceunder l
yi
ngady namicpr ogrammingal gor i
thm,wewi l
lconsi der
allpossi bleway st ochoosear ootakamongt hekeysai,...,aj.Forsuchabi nary
k−1
sear cht r
ee( Fi
gure8. 8)
,therootcontai
nskeyak, theleftsubt r
eeTi cont ainskey s
j
ai,...,ak−1 opt i
mal l
yarr
anged,andt heri
ghtsubtreeTk+1cont ainskey sak+1,...,aj
alsoopt imallyarranged.(Notehow wear et aki
ngadv antageoft hepr inci
pleof

opt
imal
i
tyher
e.)

I
fwecountt
reel
evel
sst
art
ingwi
th1t
omaket
hecompar
isonnumber
sequalt
he

DeptofCSE,
CBI
TPage14
 DAA-
18CS42—MODULE-
4 2020

key
s’l
evel
s,t
hef
oll
owi
ngr
ecur
rencer
elat
ioni
sobt
ained:

Thet wo-dimensi
onaltableinFigure8.9showsthev aluesneededf orcomput i
ngC( i,
j)
byf ormula(8.8)
:theyar einrow iandt hecolumnst otheleftofcolumnjandi n
columnjandt herowsbel ow row i.Thearrowspoi nttot hepair
sofent ri
eswhose
sumsar ecomputedinor dertofindthesmal l
estonet oberecordedast hev alueof
C(i
, j
).Thissuggestsf
ill
i
ngt hetablealongitsdi
agonal s,st
arti
ngwithallzerosont he
mai ndiagonalandgivenpr obabil
it
iespi,1≤i≤n,rightabov eitandmov ingt oward
theupperr i
ghtcorner
.
The algori
thm we j ustsket ched comput es C(1,n) —the average numberof
comparisonsf orsuccessfulsear chesintheopt imalbinar
yt r
ee.Ifweal sowantt o
gettheopt i
malt r
eeitsel
f,weneedt omai ntai
nanot hertwo-dimensionalt abl
et o
recordthevalueofkf orwhicht hemi ni
mum i n( 8.
8)isachieved.Thet ablehast he
sameshapeast hetablei
nFi gure8. 9andisf i
ll
edinthesamemanner , starti
ngwith
entri
esR(i,
i)=if or1≤i≤n.Whent hetabl
eisf il
led,i
tsentr
iesindi
cateindi cesofthe
DeptofCSE,
CBI
TPage15
 DAA-
18CS42—MODULE-
4 2020

r
oot
softheopti
malsubtr
ees,
whi
chmakesi
tpossi
blet
oreconst
ructanopt
imalt
ree
f
ort
heenti
resetgi
ven.

Example:Letusi
l
lust
rat
ethealgor
it
hm byappl
yi
ngi
ttot
hef
our
-keysetweusedat
thebegi
nningoft
hissect
ion:

Thei
nit
ial
tabl
esl
ookl
i
ket
his:

Letuscomput
eC(
1,2)
:

Thus,
outoftwopossibl
ebi nar
ytreescontai
ningthefi
rstt
wokey s,AandB,theroot
oftheopti
maltreehasi ndex2( i
.e.,i
tcontai
nsB) ,andtheav eragenumberof
compari
sonsinasuccessfulsear
chi nthi
str
eeis0.4.Onfini
shi
ngt hecomputat
ions
wegetthefol
l
owingfi
naltables:

Thus,theav er
agenumberofkeycompar isonsint heoptimal t
reeisequal to1.7.SinceR(
1,
4)=3,t her ootoft heopt imaltreecontainsthet hir
dkey ,i
.e.
,C.I tsl
ef tsubtr
eei s
madeupofkey sAandB,andi tsri
ghtsubt r
eecont ainsjustkeyD.Tof indt he
specif
icstructureoft hesesubt rees,wef i
ndf i
rstt hei
rrootsbyconsul tingther oot
tabl
eagainasf ol
lows.SinceR( 1, 2)=2,therootoft heopt i
malt r
eecont aini
ngAand
BisB, wit
hAbei ngitsleftchil
d(andt herootoft heone- nodetree:R(1,1)=1) .Si
nce
R(4,4)=4, therootoft hi
sone- nodeopt i
maltreei sitsonlykeyD.Fi gur
egi venbelow
presentst
heopt i
mal t
reei nit
sent ir
ety
.

DeptofCSE,
CBI
TPage16
 DAA-
18CS42—MODULE-
4 2020

Her
eisPseudocodeoft
hedy
nami
cpr
ogr
ammi
ngal
gor
it
hm.

5.
Knapsackpr
obl
em
Westartt
hissect
ionwi
thdesi
gni
ngady
nami
cpr
ogr
ammi
ng f
ort
heknapsack
al
gor
ithm

probl
em: gi
vennitemsofknownwei
ghtsw1,...,wnandval
uesv1,
...,vnanda
knapsackofcapacit
yW,fi
ndthemostv
aluablesubsetoft
heit
emst hatf
iti
ntot
he
knapsack.
Todesi gnadynamicprogr
ammi ngal
gori
thm,weneedtoder
ivear
ecur
rencerel
ati
onthat
expressesasoluti
ontoaninst
anceoftheknapsackpr
obl
em i
n ofsol
uti
onstoits
ter
mssmal l
ersubi
nst
ances.

DeptofCSE,
CBI
TPage17
 DAA-
18CS42—MODULE-
4 2020

Letusconsideraninstancedefi
nedbythef i
rstiitems,1≤i≤n,wit
hweightsw1, ...,
wi,val
uesv1,...,vi,andknapsackcapacit
yj ,1≤j≤W.LetF( i
,j
)bethevalueofan
opti
malsoluti
ont othisinst
ance.Wecandi videallthesubset
softhefirstiit
ems
thatfi
ttheknapsackofcapacityji
ntotwocat egori
es:thoset
hatdonotincludethe
th
ii t
em andthosethatdo.Notethefol
lowing:
th
i. Amongt hesubset st hatdonoti ncl
udethei i
tem,theval
ueofanoptimal
subsetis, bydefi
nit
ion,F(i−1,j)
.
t
h
i
i
. Amongt hesubset sthatdoi ncl
udethei i
tem (hence,j−wi≥0),anopt
imal
subsetismadeupoft hi
sitem andanoptimalsubsetoft hef
ir
sti−1it
ems
thatfi
tsi nt ot
heknapsackofcapaci tyj−wi.Thev al
ueofsuchanoptimal
subsetisv i+F(
i−1, j−wi).

Thus,
thev
alueofanopti
malsol
uti
onamongal
lfeasi
blesubset
soft
hef
ir
stIi
tems
i
sthemaxi
mum ofthesetwoval
ues.

I
tisconv
eni
entt
odef
inet
hei
nit
ial
condi
ti
onsasf
oll
ows:
F(
0,j
)=0f
orj
≥0andF(
i,0)=0f
ori
≥0.
Ourgoali
stofindF(n,
W) ,
themaxi
malv
alueofasubsetofthengi
veni
temst
hat
fi
tint
otheknapsackofcapaci
tyW,
andanopti
malsubsetit
self
.

Exampl
e-1:
Letusconsi
dert
hei
nst
ancegi
venbyt
hef
oll
owi
ngdat
a:

Thedy
nami
cpr
ogr
ammi
ngt
abl
e,f
il
ledbyappl
yi
ngf
ormul
asi
sgi
venbel
ow

DeptofCSE,
CBI
TPage18
 DAA-
18CS42—MODULE-
4 2020

Thus,
themaxi
mal
val
uei
sF(
4,5)=$37.

Wecanf indthecomposi t
ionofanopt i
malsubsetbybackt r
acingthecomput ati
ons
oft hisentr
yi nthet able.SinceF( 4,5)>F( 3,5),i
tem 4hast obei ncludedi nan
optimalsoluti
onal ongwi t
hanopt i
malsubsetf orfi
l
ling5−2=3r emaininguni t
sof
theknapsackcapaci t
y.Thev alueofthelatt
erisF(3,3).SinceF(3,3)=F( 2,3),
item 3
neednotbei nanopt i
mal subset.SinceF(2,3)>F(1,3),i
tem 2isapar tofanopt i
mal
selecti
on,whichl eavesel ementF( 1,3−1)t ospeci f
yit sremainingcomposi t
ion.
Similarl
y,si
nceF(1, 2)>F(0,2), i
tem 1isthefi
nalpartoftheopt i
malsol ut
ion{item 1,
i
tem 2, i
tem 4}.

Anal
ysi
s
Theti
meef
fici
encyandspaceeffi
ciencyoft
hisal
gori
thm ar h Θ(
ebot nW)
.Thet
ime
i
nneededt
of i
ndthecomposit
ionofanopt i
malsol
uti
onisinO(
n).

Memor
yFunct
ions
Thedirectt
op-
downapproacht
ofi
ndi
ngasol
uti
ont
osuchar ecur
rencel
eadst
oan
al
gori
thm thatsol
vescommonsubprobl
emsmorethanonceandhencei sver
y
i
neff
ici
ent.
Thecl assicdynami cprogr
ammi ngappr oach, ontheotherhand, worksbot
tom up:i
t
fi
ll
sat ablewi t
hsol ut
ionstoall
smal l
ersubpr oblems,buteachoft hem i
ssolv
edonly
once.Anunsat isfyi
ngaspectoft hisappr oachi sthatsolut
ionst osomeoft hese
smal l
ersubpr oblemsar eoft
ennotnecessar yforgetti
ngasol utiontotheprobl
em
given.Sincethisdrawbackisnotpr esentinthetop-downappr oach,iti
snatur
alt
ot r
y
tocombi net hest r
engthsofthetop-downandbot tom-upapproaches.Thegoalisto
getamet hodthatsolvesonlysubproblemst hatare
necessar yanddoesso once.Suchamet hodexi st
s;iti
s onusi
ngmemor y
only based
functi
ons.

Thismet hod solvesa gi ven problem i nt he top-down mannerbut ,in addi t

ion,
maintai
nsat ableoft heki ndthatwoul dhav ebeenusedbyabot tom-updy nami c
programmingal gori
thm.Initi
all
y,allthet abl
e’ sentri
esarei ni
ti
ali
zedwi t
haspeci al
“nul
l”symboltoindicatethattheyhav enoty etbeencal cul
ated.Thereaft
er, whenev er
anew v al
ueneedst obecal culat
ed,t hemet hodcheckst hecorrespondingent ryi n
thetabl
efirst
:ifthi
sent r
yisnot“ null
,”iti
ssimpl yretri
evedfrom t
het abl
e; otherwise,
i
tiscomput edbyt herecursiv
ecal lwhoser esultisthenrecordedinthetable.
The f
ollowi
ng al
gori
thm implementsthisidea f
orthe knapsackproblem.Af
ter
i
nit
ial
i
zingthet
able,ther
ecursiv
efuncti
onneedstobecalledwithi=n(thenumber
ofi
tems)andj=W ( t
heknapsackcapaci
ty)
.
Al
gori
thm MFKnapsack(
i,j
)
//
Impl
ementsthememor yfunct
ionmet
hodf
ort
heknapsackpr
obl
em
DeptofCSE,
CBI
TPage19
 DAA-
18CS42—MODULE-
4 2020

/
/Input
:Anonnegat i
veintegerii
ndicat
ingt henumberofthefirstitemsbei
ng
consi
deredandanonnegat iveintegerji
ndicati
ngtheknapsack
capaci
ty
/
/Output:Thevalueofanopt i
mal f
easiblesubsetofthefi
rstiitems
/
/Note:Uses as gl obalv ari
ables input arrays Weights[1.
.n],V
alues[
1..
n],andtableF[0.
.n,0..
W ]whoseent ri
esarei nit
iali
zed
with−1’sexceptforrow0andcol umn0i nit
ial
i
zedwith0’ s

DeptofCSE,
CBI
TPage20
 DAA-
18CS42—MODULE-
4 2020

Example-2Letusapplythememor yfuncti
onmethodtotheinstanceconsi
der
edin
Example
1.Thet abl
ei nFiguregivenbelow giv
est her
esult
s.Only11outof20nont ri
vial
val
ues( i
.e.
,nott hoseinr ow 0ori ncolumn0)hav ebeencomput ed.Justone
nontr
ivi
alentry,V (1,2),isr et
ri
eved rat
herthan bei
ng recomputed.Forlar
ger
i
nstances,t
hepr oport
ionofsuchentr
iescanbesigni
fi
cantl
ylarger.

Fi
gur
e:Exampl
eofsol
vi
ngani
nst
anceoftheknapsackpr
obl
em byt
hememor
yfunct
ion
algor
it
hm

Ingeneral
,wecannotexpectmorethanaconstant-
fact
orgai
ninusingt
hememory
funct
ionmet hodfort
heknapsackprobl
em,becauseitsti
meeff
ici
encycl
assi
sthe
sameast hatofthebot
tom-upal
gor
ithm

6.
Bel
lman-
For
dAl
gor
it
hm (
Singl
esour
ceshor
testpat
hwi
th–v
ewei
ght
s)
Pr
obl
em def
ini
ti
on
Singl
esourceshor t
estpat
h-Gi v
enagr aphandasourcever
texsingr
aph,f
ind
short
estpathsfrom st oallv
ert
icesi
nt hegi
vengr
aph.Thegraphmaycont
ain
negati
veweightedges.
Notethatwehav ediscussedDi jkst
ra’
salgor
ithm f
orsinglesour
ceshort
estpat
h
probl
em.Dij
ksr
a’salgor
ithm isaGr eedyal
gori
thm andtimecomplexi
tyi
sO(Vl
ogV).
ButDij
kst
radoesn’
tworkf orgraphswi t
hnegat
iveweightedges.
Bel
lman-
Fordworksforsuchgraphs.Bel
l
man-
For
disal
sosimpl
ert
hanDijkst
raand
sui
teswellf
ordist
ri
butedsyst
ems.Butt i
mecompl
exi
tyofBel
l
man-For
di sO(VE)
,
whi
chismorethanDij
kstr
a.
Howi
twor
ks?
LikeotherDynamicPr ogrammi ngProbl ems,thealgorithm calculat
esshor t
estpathsin
bottom-upmanner .Itfir
stcal culat
est heshortestdist ancesf ortheshortestpaths
whichhav eat-
mostoneedgei nthepat h.Then,itcalculatesshortestpathswithat-
th
most2edges,andsoon.Af terthei i terati
onofout erl oop,theshortestpathswith
atmostiedgesar ecalculated.Ther ecanbemaxi mum | V|–1edgesi nanysi mple
path,t
hatiswhyt heout erloopr uns|v |–1t imes.Thei deai s,assumingthatthereis
nonegat i
veweightcy cl
e,ifwehav ecal cul
atedshortestpat hswi thatmostiedges,
thenani t
erati
onov eralledgesguar ant eestogiv eshor testpathwithat-most( i
+1)

DeptofCSE,
CBI
TPage21
 DAA-
18CS42—MODULE-
4 2020

edges

Bel
l
man-
For
dal
gor
it
hm t
ocomput
eshor
testpat
h

DeptofCSE,
CBI
TPage22
 DAA-
18CS42—MODULE-
4 2020

7.
Trav
ell
ingSal
esPer
sonpr
obl
em (
T2:
5.9)
,

DeptofCSE,
CBI
TPage23
 DAA-
18CS42—MODULE-
4 2020

DeptofCSE,
CBI
TPage24
 DAA-
18CS42—MODULE-
4 2020

DeptofCSE,
CBI
TPage25
 DAA-
18CS42—MODULE-
4 2020

8.
Rel
iabi
li
tydesi
gn

DeptofCSE,
CBI
TPage26
 DAA-
18CS42—MODULE-
4 2020

DeptofCSE,
CBI
TPage27
DAA-
18CS42—MODULE-
4 2020