CS61b final study guide PDF

Preview

Summary

Download CS61b final study guide PDF

Description

CS6 1 bfin a ls t u d yg u i d e Le c t ur e2 7 :De c o mpo s i t i o nandRe duc t i o ns  T op o l o g i c a lSo r t i n g  S ho r t e s t Pa t h so nDAGs  Lo n g e s tPa t h s  Re d u c t i o n s 

Pr o b l e m

Pr o b l e m De s c r i p t i on

So l ut i o n

pa t hs

Fi n dap a t hf r o mst oe v e r y r e a c h a b l ev e r t e x .

De pt h Fi r s t Pa t h s . j a v a De mo

O( V+E)t i me Θ( V)s p a c e

s h o r t e s t pa t hs

Fi n dt h es h o r t e s tp a t hf r omst o e v e r yr e a c h a b l ev e r t e x .

Br e a d t h Fi r s t Pa t h s . j a v a De mo

O( V+E)t i me Θ( V)s p a c e

s h o r t e s t we i g h t e d pa t hs

Fi n dt h es h o r t e s tp a t h , c o n s i d e r i n gwe i gh t s , f r o mst o e v e r yr e a c h a b l ev e r t e x .

Di j k s t r a s SP . j a v a De mo

s h o r t e s t we i g h t e d pa t h

Fi n dt h es h o r t e s tp a t h ,c o ns i d e r A* :Sa mea sDi j k s t r a ’ sb u twi t hh ( v , we i g h t s , f r omst os o met a r g e t g o a l )a d de dt op r i o r i t yo fe a c hv e r t e x . v e r t e x De mo

Pr o b l e m

Pr o b l e mDe s c r i p t i o n

So l u t i o n

mi ni mu ms pa n ni n gt r e e Fi ndami n i mu ms p a n ni n gt r e e . La z y Pr i mMST. j a v a De mo

Effic i e n c y

O( El o gV) t i me Θ( V)s p a c e Ti med e p e nd s o nhe u r i s t i c . Θ( V)s p a c e

Effic i e n c y O( ? ? ? )t i me Θ( ? ? ? )s p a c e

mi ni mu ms pa n ni n gt r e e Fi ndami n i mu ms p a n ni n gt r e e . Pr i mMST. j a v a De mo

O( El o gV)t i me Θ( V)s p a c e

mi ni mu ms pa n ni n gt r e e Fi ndami n i mu ms p a n ni n gt r e e . Kr u s k a l MST. j a v a De mo

O( El o gE)t i me Θ( E)s p a c e

To p o l o g i c a ls o r t i n g Pe r f o r maDFSt r a v e r s a lf r o me v e r yv e r t e xwi t hi n d e g r e e0 ,NOTc l e a r i n gma r ki n g si nb e t we e nt r a v e r s a l s . 

Re c or dDFSp o s t o r d e ri nal i s t .



Top o l o g i c a lor d e r i n gi sg i v e nb yt her e v e r s eo ft ha t l i s t( r e v e r s ep o s t o r d e r ) .

c a nt h i n ko ft h i sp r o c e s sa ss o r t i n gou rn o d e ss ot h e ya p p e a ri na no r d e rc on s i s t e ntwi t he dg e s ,e . g . [ 2 ,5 , 6 , 0 , 3, 1 , 4 , 7 ] 

Wh e nno d e sa r es o r t e di nd i a g r a m, a r r o wsa l lp o i n tr i g ht wa r d s .



Wer e s t a r t wi t hi n d e g r e e 0

An ot h e rb e t t e rt o p o l o g i c a ls o r t a l g or i t h m:

  

Ru nDFSf r o ma na r b i t r a r yv e r t e x . I fn o ta l lma r k e d ,p i c ka nun ma r k e dv e r t e xa n dd oi ta g a i n . Re p e a tu n t i ldo n e .

At o p o l o g i c a ls o r t o nl ye x i s t si ft heg r a p hi sad i r e c t e da c y c l i cg r a p h( DAG) . 

Fort h egr a p hb e l o w, t he r ei sNOp o s s i b l eo r d e r i n gwh e r ea l la r r o wsa r er e s p e c t e d .

DAGsa p p e a ri nma n yr e a lwo r l da p p l i c a t i o n s , a n dt he r ea r ema n yg r a p ha l g o r i t h mst h a to n l ywo r konDAGs . I fwea l l o wne g a t i v ee d g e s ,Di j k s t r a ’ sa l g o r i t hmc a nf a i l .  

Fore x a mp l e , b e l o wwes e eDi j ks t r a ’ sj u s tb e f o r ev e r t e x2i sv i s i t e d . Re l a x a t i o no n4s u c c e e d s , b u td i s t a nc et o5wi l ln e v e rb eup d a t e d .

On es i mp l ei d e a :Vi s i tv e r t i c e si nt o p o l o g i c a lor d e r . One a c hv i s i t , r e l a xa l lo u t g oi n ge d g e s . Ea c hv e r t e xi sv i s i t e do n l ywh e na l lp o s s i b l ei nf oa b o uti th a sb e e nu s e d ! Ei st h et o t a ln u mb e ro fe dg e si nt h ee n t i r eg r a p h ,no tt h en u mb e ro fe d g e sp e rv e r t e x  

Lo n g e s tp a t h so ng r a p hp r ob l e m-s t i l lu n s o l v e d DAGLPTo nd i r e c t e da c y c l i cg r a p hs o l u t i o nf org r a phG:  

For man e wc o p yo ft heg r a p hG’wi t hs i g n so fa l le dg ewe i g h t sfli p p e d . Ru nDAGSPTo nG’y i e l di n gr e s ul tX.



Fl i ps i g n so fa l lv a l u e si nX. d i s t To . X. e d g e Toi sa l r e a d yc o r r e c t .

Gi v e nag r a p hG,wec r e a t e dan e wg r a p hG’a ndf e di tt oar e l a t e d( b u td i ffe r e n t )a l g o r i t h m, a n dt h e ni n t e r p r e t e d t h er e s u l t .

-

Th i sp r o c e s si skn o wna sr e duc t i o n.

 

Si n c eDAGSPTc a nb eu s e dt os o l v eDAGLPT ,wes a yt h a t“ DAGLPTr e d u c e st oDAGSPT” . I fa n ys u b r o u t i n ef o rt a s kQc a nb eu s e dt os o l v eP , wes a yPr e d uc e st oQ. ”

Le c t ur e2 9 :Sor t i ngI  Th eSo r t i n gPr o b l e m  S e l e c t i onSo r t , He a ps o r t  Me r g e s o r t  I n s e r t i o nSo r t Ano r de r i ngr e l a t i o n...