Algorithm Design and Analysis
Algorithm Design and Analysis CSE 565
Popular in Course
Popular in Computer Science and Engineering
This 0 page Class Notes was uploaded by Libby Kuhlman on Sunday November 1, 2015. The Class Notes belongs to CSE 565 at Pennsylvania State University taught by Staff in Fall. Since its upload, it has received 18 views. For similar materials see /class/233118/cse-565-pennsylvania-state-university in Computer Science and Engineering at Pennsylvania State University.
Reviews for Algorithm Design and Analysis
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/01/15
Algorithm Design and Analysis LECTURE 8 Greedy Graph Algorithms Shortest Paths 39Dijkstra s Minimum Spanning Tree 39Kruskal s Prim s 39ReverseDelete Sofya Raskhodnikova W s mmmm bmdomiyw by a 0mm 5 ursersomA min K wbym 9 Review Question 0 Express Evev degregv in terms of m the number of edges in the undirected graph Handshaking Lemma Zvev degreev 2 IE I for undirected graphs 0 When a priority queue is impemented using an unsorted array how long do ExtractMin and DecreaseKey take Answer ExtractMin 7 0n DecreaseKey 7 01 W s Rastdwbnlwwz basean was by a 0mm 5 ursemmA min K wbym gl Shortest Path Problem 0 Input 7 Directed graph G V E 7 Source node 5 destination node t 7 for each edge e length 6 length of e 0 Find shortest directed path from s to t a 3quot 39 I n q Lengm uf path 62350 15 s 392321650 2n 7 d V 5 Wm s mmmm bmdomiyw by a 0mm 5 ursersomA min K wbym g Dijkstra39s Algorithm Greedy 0 Maintain a set of explored nodes S Whose shortest path distance du from s to u is known 0 Initialize S s ds O 0 Repeatedly choose unexplored node V which minimizes 39 hm 2 a h asame ume lured 7 m s 1 3 pmfm yfy iiyagmgb 21 it y 47w is 0 add V to S and set dV 71V WW s Rastdwbnlwwz basean was by a 0mm 5 ursemmA min K Wayne gl Dijkstra39s Algorithm Greedy 0 Maintain a set of explored nodes S Whose shortest path distance du from s to u is known 0 Initialize S s ds 0 Repeatedly choose unexplored node V which minimizes Vgt5 yi zsd gt ltegtv moistLzzezgtzzgz m 0 add V to S and set dV 71V 12 WW s mmmm bmdomiyw by a 0mm 5 ursersomA min K wbym Proof of Correctness Invariant For each node u e S du is the length of the shortest path from s to u P Proof byinduction on Si 0 Base case S 1 is trivial s 0 Inductive hypothesis Assume for S k 2 l 7 Let V be next node added to S and let by be the chosen edge 7The shortest sru path plus uv is an srv path of length 11v 7 Consider any srv path P We39ll see that it39s no shorter than 11v 7Let xry be the rst edge in P that leaves S and let P39 be the subpath to x 7 P xygt has length g dxgt lxygt nygt nvgt ywmq S Rasldwah ileum basean was by a 0mm 5 ursemmA min K wbym Implementation iNext node to explore node with rninirnurn 75V 7When exploring V for each edge e VW update 39wmin 721w 702 Ne Ef cient implementation Maintain a priority queue of unexplored nodes prioritized by TCV mum s Ru wamlwvm bmdomiyw by a Dmm 5 14mm 3an K wbym For unexplored nodes maintain 7110 minsdu2e Demo of Dijkstra s Algorithm Graph with nonnegative edge lengths Wm s Ru wamlwvm bmdomiyw by a Dmm 5 14mm 3an K wbym Implementation of DijkstraG E ds e o for each v e V7 s o dv e co TEV e co Q Q e V D Q is apriority queue maintaining V7 S V While Q Q do u e EXTRACTMINQ s e s o u dm e m for each v e Adjacencylistu explore do at New UH EX edges in 5 Wm V leavirgv lmpllclt DECREKAgE EY byquot s Rasldwamlwwz basean was by a 0mm 5 lmersonA my mI Demo of Dijkstra s Algorithm Initialize SSH mum s Rasldwamlwwz basean was by a 0mm 5 lmersonA 3an K Wayne El Demo of Dijkstra s Algorithm A lt EXTRACTMINQ SA W s Ru wamlwwz bamsz by E 0mm c14iwsmASrmn K wbyu WI Demo of Dijkstra s Algorithm SA WW 3 Rasldwamlwwz basean was by a 0mm 5 lmersonA 3an K wbym El Demo of Dijkstra s Algorithm SAC W s Ru wamlwwz bmboylsnw by a DmmCl 1sersovLASm1 L K wbym El Demo of Dijkstra s Algorithm 7 11 2 Explore edges leaving C SAC W s Rasldwamlwm bmbon was by a Dmme c l1ursonA 3an K wbym El Demo of Dijkstra s Algorithm 7 11 39 2 E EXTRACTMINQ Q B 07777 3 5 103mm SACE WW 3 Ru wamlwwz bmboylsnw by a DmmCl 1sersovLASm1 L K wbym I Demo of Dijkstra s Algorithm Explore edges leaving E 7 11 5 7 11 SSACE WW 3 Rasldwamlwm bmbon was by a Dmme c l1ursonA 3an K Wayne gl Demo of Dijkstra s Algorithm 7 11 B lt EXTRACTMINQ 2 a 10 3 2 D G 2 9 O m m m m 3 5 1o 3 m m 7 11 5 7 11 SSACEB WW 3 Ru wamlwwz bmboylsnw by a DmmCl 1sersovLASm1 L K wbym I Demo of Dijkstra s Algorithm Explore edges leaving B 7 9 2 D G 9 O m w w w 3 5 1o 3 w w 7 11 5 7 11 SSACEB mm 9 s Rasldwamlwm bmbon was by a Dmme c l1ursonA 3an K wbym mI Demo 0f Dijkstra s Algorithm 7 11 SffAycyEyByD mum 9 s Ru wamlwva baxedonslia by E Dmm 5 mm min K wbym mI Analysis of Dijkstra While Q Q do u 7 EXTRACTMINQ e S w u n a for each v E Adju ti mes deg2200 do ifdv gt du Wu y times then du e du Wu y Handshaking Lemma gt gm implicit DECREASEKEYS itsquot la gn W3 1 miogm mlag np Wm mm r Individual bps 02 mum hm s mmmm bmbbn was by a 0mm 5 L4memmA mist K wbym Minimum spanning tree MST Input A connected undirected graph G V E E 7 R with weight function w For now assume all edge weights are distinct Output A spanning tree T7 a tree that connects all vertices 7 of minimum weight wT Z wuv 14va WW 3 mmmm bmbbmiyw by a Dmm c laum tA mist K wbym Example of MST W s mmmm bmbbn was by a 0mm 5 L4memmA mist K Wayne g Example of MST P W s Rubwbbntwyb hexadovmluia by E 0mm 5 Wm min K wbyu Applications 0 Network design 7 telephone electrical hydraulic TV cable computer road Approximation algorithms for NPhard problem 7 traveling salesperson problem Steiner tree 0 Indirect applic ations 7 max bottleneck paths 7 LDPC codes for error correction 7 image registration with Renyi entro 7 learning salient features for real7time face verification 7 reducing data storage in sequencing amino acids in a protein 7 model locality of particle interactions in turbulent uid ows 7 autocorl fig protocol for Ethemet bridging to avoid cycles in a S 0 Cluster analysis WW 3 mmmm bmbbn was by a 0mm 5 L4memmA mist K wbym g Greedy Algorithms for MST Kruskal39s Start with T if Consider edges in ascending order of weights Insert edge e in T unless doing so would create a cyc e ReverseDelete Start with T E Consider edges in descending order of weights Delete edge e from T unless doing so would disconnectT Prim39s Start with some root node 3 Grow a tree T from s outward At each step add to T the cheapest edge e with exactly one endpoint in T W s mmmm bmbomiyw by a Dmm c hisersomA min K wbym g Cut and Cycle Properties Cut property Let S be a subset of nodes Let e be the min weight edge with exactly one endpoint in S Then the MST contains e Cycle property Let C be a cycle and let f be the max weight edge in C Then the MST does not contain f f c EV 7 OO eismtbeMST fisnutmtbeMST mum s Rasldwahilwva bmbon was by a 0mm 5 lmersoviA min K wbym gl Cycles and Cuts Cycle Set of edges the form abbccdyzza 0 k a 9 Cut2 a subset of nodes S The corresponding cutset D is the subset of edges with exactly one endpoint in S Eyelet t2Lzaa t4aaaat WW 3 mmmm bmbomiyw by a Dmm c hisersomA min K wbym g CycleCut Intersection Claim A cycle and a cutset intersect in an even number of edges Proof A cycle has to leave and enter the cut the same number of times C WW 3 Rasldwahilwva bmbon was by a 0mm 5 lmersoviA min K Wayne gl Proof of Cut Property Cut property Let S be a subset of nodes Let e be the min weight edge with exactly one endpoint in S Then the MST T contains e Proof2 exchange argument 5 7 Suppose e does not belong to T 7 Adding e to T creates a cycle C in T T 7 Edge e is both in the cycle C and in the cutset D corresponding to S gt there exists another edge say f that is inboth C and D 7T39 T U e 7 f isalsoa spanningtree 7 Since cc lt cf costT39 lt costTgt Contradiction WW 3 mmmm bmbomiyw by a Dmm c hisersomA min K wbym Proof of Cycle Property Cycle property Let C be a cycle in G Let fbe the max weight edge in C Then the MST T does not contain f Proof2 exchange argument 5 39 7 Suppose fbelongs to T 7 Deleting f from T creates a cut S in T 7Edge fis both in the cycle C and in the cutset D corresponding to S gt there exists another edge say e that is in both C and D 7T39 T U e 7 f isalsoa spanningtree 7 Since cc lt cf costT39 lt costTgt Contradiction WW 3 Rasldwahilwva bmbon was by a 0mm 5 lmersoviA min K wbym Algerithm Design and Analysis m LECTURE 8 0 Max lateness cont d fa A K i 1 10oll 39f Optimal Caching Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 9122008 Scheduling To Minimizing LaTeness Minimizing laTeness problem Single resource processes one job aT a Time Job j requires TJ uniTs of processing Time and is due aT Time dj Ifj sTarTs aT Time s iT finishes aT Time fJ sJ TJ LaTeness Q max 0 fj dJ Goal schedule all jobs To minimize maximum laTeness L max 3 1 5 Ex I tj 3 2 1 4 3 2 68991415 lateness 2 lateness O max lateness 6 l l l d39 d28 d615 d16 d514 d49 1 2 3 4 5 6 7 8 9 1O 11 12 13 14 15 Minimizing La reness Greedy Algor i rhms Gr39eedy Templa re Consider jobs in some order Shor39TesT processing Time fir39sT Consider39 jobs in ascending order of processing Time TJ Ear39lies l39 deadline fir39sT Consider39 jobs in ascending order of deadline dJ SmallesT slack Consider39 jobs in ascending order of slack dJ TJ Minimizing La reness Greedy Algor39i rhms Gr39eedy Templa re Consider jobs in some order Shor res r processing Time fir39sT Consider39 jobs in ascending order of processing Time TJ tj 1 10 counterexample SmallesT slack Consider39 jobs in ascending order of slack dJ TJ j counterexample Minimizing La reness Greedy Algor i rhm Greedy algor39i rhm Ear39lieS r deadline first d16 Sort n jobs by deadline so that 11 5 d2 5 s dn t 0 for j l to n Assign job j to interval t t t sjlt tfjlt ttj t t tj output intervals sj f1 3 max lateness 1 1 d2 8 d39 d49 Minimizing La reness No Idle Time Obser39vcrrion There exists an optimal schedule wi rh no idle Time d4 d6 d12 O 1 2 3 4 5 6 7 8 9 1O d4 d6 d12 O 1 2 3 4 5 6 7 8 9 1O Obser39vcrrion The greedy schedule has no idle Time Minimizing Lo reness Inver39sions Def An inversion in schedule 5 is a pair39 of jobs i and j such That i lt j bu rj scheduled before i inversion Obser39vcrrion Gr39eedy schedule has no inver39sions Obser39vcrrion If a schedule with no idle Time has an inversion if has one with a pair39 of inverted jobs scheduled consecu rively Minimizing LaTeness Inver39sions Def An inversion in schedule 5 is a pair39 of jobs i and j such ThaT i lt j buTj scheduled before i inversion 1 1 i lquotj Claim Swapping Two adjacenT inver39Ted jobs r39educes The number39 of inver39sions by one and does noT increase The max laTeness Pf LeT E be The laTeness before The swap and leT E 39 be iT afTer39war39ds E39k kfor39all k ij I Eli S i J fJ dj definiTion If JOlDJ IS laTe fldJ J finishes aT Timefi s f C i lt J 5 El definiTion Minimizing LaTeness Analysis of Greedy AlgoriThm Theorem Greedy schedule 5 is opTimal Pf Define 5 To be an opTimal schedule ThaT has The fewesT number of inversions and leT39s see whaT happens Can assume 5 has no idle Time If 5 has no inversions Then 5 5 If 5 has an inversion eT ij be an adjacenT inversion swapping i and j does noT increase The maximum laTeness and sTrichy decreases The number of inversions This conTradicTs definiTion of 5 Greedy Analysis STraTegies Greedy algoriThm sTays ahead Show ThaT afTer each sTep of The greedy algoriThm iTs soluTion is aT leasT as good as any oTher algoriThm39s Exchange argumenT Gradually Transform any soluTion To The one found by The greedy algoriThm wiThouT hurTing iTs qualiTy STrucTural Discover a simple quotsTrucTuralquot bound asserTing ThaT every possible soluTion musT have a cerTain value Then show ThaT your algoriThm always achieves This bound 43 Op rimal Caching Op rimal Offline Caching Caching Cache wi rh capaci ry To store k i rems Sequence of m i rem r39eques rs d1 d2 dm Cache hiT iTem already in cache when requested Cache miss i rem noT already in cache when requested must bring r39eques red i rem in ro cache and evicT some exisTing i rem if full Goal EvicTion schedule Tha r minimizes number39 of cache misses Ex k 2 ini rial cache ab requests a b c b c a a b Op rimal evicTion schedule 2 cache misses 0399 039 m man on m O39O39O39O39O39O39O39O39 requests cache Sugges rions for39 greedy approaches OpTimal Offline Caching Far39ThesTInFuTur39e Far39ThesTinfuTur39e EvicT iTem in The cache ThaT is noT r39equesTed unTiI far39ThesT in The fuTur39e current cache a b c d e f futurequerieSI gabcedabbacdeafadefgh T 1 cache miss eject this one Theor39em Bellady 19605 FF is opTimaI evicTion schedule Pf Algor39iThm and Theorem ar39e inTuiTive proof is subTIe Reduced Evic rion Schedules Def A reduced schedule is a schedule That only inser39Ts an item info The cache in a sTep in which Tha r item is requested InTuiTion Can Transform an unreduced schedule info a reduced one with no more cache misses Idea is To defer39 unreduced r39equesTs Pr39oof will be an exercise aabc aa aac aa cane ca dad da aab aa bab ba cacb ca aabc aa aabc aa an unreduced schedule a reduced schedule FarThesTInFuTure Analysis Theorem FF is opTimal evicTion algoriThm Pf by inducTion on number or requesTs j InvarianT There exisTs an opTimal reduced schedule 5 ThaT makes The same evicTion schedule as SFF Through The firsT j1 requesTs LeT S opT reduced schedule ThaT saTisfies invarianT Through j requesTs We produce 539 ThaT saTisfies invarianT afTer j1 requesTs Consider j1er requesT d dJ1 Since 5 and SFF have agreed up unTil now They have The same cache conTenTs before requesT j1 Case 1 d is already in The cache 539 S saTisfies invarianT Case 2 d is noT in The cache and S and SPF evicT The same elemenT S39 S saTisfies invarianT Far39thestInFutur39e Analysis Pf continued Case 3 d is not in the cache SPF evicts e S evicts 1 e begin construction of 539 from S by evicting e instead of f j same e 1 same e f j1 same e d same d f now 539 agrees with SFF on first j1 requests we show that having element 1 in cache is no worse than having element e Far39ThesTInFuTur39e Analysis LeT j39 be The fir39sT Time afTer39 j1 ThaT S and 539 Take a differenT acTion and eT g be ITem r39equesTed aT TIme J must involvee or f orboth r f S 839 Case 3a 9 e Can39T happen wiTh Far39ThesTInFuTur39e since Ther39e musT be a r39equesT for39 1 before e Case 3b 9 f EIemenT f can39T be in cache of 5 so eT e39 be The elemenT ThaT S evicTs if e39 e S39 accesses T from cache now 5 and 539 have same cache if e39 e S39 evicTs e39 and brings e inTo The cache now 5 and 539 have The same cache Note 839 is no longer reduced but can be transformed into a reduced schedule that agrees with SFF through stepj1 Far39ThesTInFuTur39e Analysis LeT j39 be The fir39ST Time afTer39 j1 ThaT S and 539 Take a differenT acTion and eT g be iTem r39equesTed aT Time j39 must involve e or f or both iquot S 839 otherwise 839 would take the same action Case 3c 9 e f S musT evicT e Make 539 evicT 1 now 5 and 539 have The same cache r 8 SI Caching Perspecfive Online vs offline algor39ifhms Offline full sequence of requests is known a priori Online r39ealify requests are not known in advance Caching is among mosf fundamen l39al online problems in CS LIFO Evicf page brought in most recently LRU Evicf page whose most recent access was ear39liesf FF with direction oftime reversed Theor39em FF is optimal offline evicfion algor39ifhm Pr39ovides basis for39 understanding and analyzing online algor39ifhms LRU is kcompefifive Section 138 LIFO is ar39bifr39ar39ily bad
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'