### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 695 Note 8 for CSE 565 at PSU

### View Full Document

## 45

## 0

## Popular in Course

## Popular in Department

This 5 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Pennsylvania State University taught by a professor in Fall. Since its upload, it has received 45 views.

## Similar to Course at Penn State

## Reviews for 695 Note 8 for CSE 565 at PSU

### 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: 02/06/15

Algorithm Design and Analysis LECTURE 8 m Greedy Graph Algorithms Shortest Paths 39Dijkstra s Minimum Spanning Tree 39Kruskal s Prim s ReverseDelete Sofya Raskhodnikova W s Ruldwahllwwz madanshda by a 0mm 5 ursersomA min K wbym Review Question 0 Express Zvev 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 mum s macaw bmbon was by a 0mm 5 ursemmA min K wbym g Shortest Path Problem 0 Input 7 Directed graph G V E 7 Source node s destination node t 7 for each edge e length 6 length of e 0 Find shortest directed path from s to t a a 3 39 n Q Lengmumm 2150 5 s 592321650 2n 39 av s Ruldwahllwwz madanshda by a 0mm 5 ursersomA min K wbym Wm 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 v min 14 23 hmtm athtngame m2 lured 7 my 0v 0 add V to S and set dV 71V Wm s macaw bmbon was by a 0mm 5 ursemmA min K wbym El 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 my In S do 43 mm women mama pan MW hyugmgb W t y 0 add V to S and set dV 71V 12 WW s Ruldwahllwwz madanshda by a 0mm 5 ursersomA min K wbym 7 P W has length dltxgt am nltygts nltvgt g 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 lSl 1 is trivial Inductive hypothesis Assume for S k 2 l 7 Let V be next node added to S and let lav be the chosen edge 7 The 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 s Rastdwahilwwz mm arm by E Deming G 1mm A min K wbym Implementation For unexplored nodes maintain 71vwrnigsdu2e iNext node to explore node with minimum 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 W s Ru wamlwva bandwishde by a Dmm c laurwmA 3an K wbym Implementation of DijkstraG E ds e o for each v e V7 s do dv e no 7rv e no S e Q Q e V D Q is apriority queue maintaining V7 S keyed on TEV While Q Q do u e EXTRACTMINQ s e s o u dm e m for each v e Adjacencylistu explore edges r I quotW leavin v lmplicrt DECREASE BY 3 Resdwamlwva basean was by a 0mm 5 L4memmA 3an K wbym mum Demo of Dijkstra s Algorithm Graph with nonnegative edge lengths WW 3 Ru wamlwva bandwishde by a Dmm c laurwmA 3an K wbym Demo of Dijkstra s Algorithm Initialize SSH m s Resdwamlwva basean was by a 0mm 5 L4memmA 3an K Wayne Demo of Dijkstra s Algorithm SA WW 3 Ru wamlwva magma by a 0mm 5 142mb 3min K wbym I Demo of Dijkstra s Algorithm Explore edges leaving A SA WW 3 Rasldwamlwm basean was by a Deming c 142mb 3min K wbym Demo of Dijkstra s Algorithm SAC W s Ru wEMLIwW bmboylsnw by a Dmm c141wwmmm K wbym SAC W s Ra dwamlwwa bmbon was by a Dmme c l1ursonA 3an K wbym Demo of Dijkstra s Algorithm SACE WW 3 Ru wEMLIwW bmboylsnw by a Dmm c141wwmmm K wbym Demo of Dijkstra s Algorithm 5 7 11 SSACE WW 3 Ra dwamlwwa bmbon was by a Dmme c l1ursonA 3an K wbym I Demo of Dijkstra s Algorithm B EXTRACTMINQ O m w w w 3 5 1o 3 w w 7 11 5 7 11 SSACEB WW 3 Ru wEMLIwW bmboylszzw by a 0mm c142wmAmzn K wbym I Demo of Dijkstra s Algorithm 7 9 2 Explore edges leaving B O m w w w 3 5 1o 3 w w 7 11 5 7 11 SSACEB W7 9 5 s memmwy bmbon was by a Deming c uzmonA 3min K wbym D EXTRACTMINQ o w w w w 5 1o 3 w w 7 11 5 7 11 SffAycyEyByD 9 W SRaxldwa11lawa Medanshda by a Dmm Cl 1ersovtASm1 I K wbym Analysis of Dijkstra While Q Q do u 7 EXTRACTMINQ n s 7 s U u y for each 1 e Adju Ll mes deg2201 do ifdv gt dm Wu y times then dy 7 du web y Handshaking Lemma gt gm implicit DECREASEKEYS 1m Hwa 1m I in h HWR 1 m quot 2 m leg 71 m 1mm 1m a lag by r Wynn ups 02 mum mm W s macaw bmbon was by a 0mm 5 Lamb 3mm K wbym Minimum spanning tree MST Input A connected undirected graph G V E with weight function w E R 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 Wm SRaxldwa11lawa Medanshda by a Dmm Cl 1ersovtASm1 I K wbym Example of MST WW 3 macaw bmbon was by a 0mm 5 Lamb 3mm K Wayne Example of MST WW SRaxldwa11lawa bmboyiszzw by a 0mm 5 141mb syrisz K wbym Applications 0 Network design 7 telephone electrical hydraulic TV cable computer road Approximation algorithms for NPhard problems 7 traveling salesperson problem Steiner tree 0 Indirect applic ations 7 max bottleneck paths 7LDPC codes for error correction 7 image registration with Renyi entropy 7 leaming salient features for real7time face verification 7 reducing data storage in sequencing amino acids in a protein 7model locality of particle interactions in turbulent uid ows 7 autoconfig protocol for Ethemet bridging to avoid cycles in a network 0 Cluster analysis WW 3 macaw bmbon was by a Deming c 141mb syrisz 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 cycle 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 5 14mm 3an 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 a SB 2OCI eismtbeMST fisnutmtbeMST W s macaw bmbon was by a 0mm 5 L4memmA 3an K wbym Cut2 a subset of nodes S The corresponding cutset D is the subset of edges with exactly one endpoint in S 4 5 8 Mira3414351 WW 3 mmmm bmbomiyw by a Dmm 5 14mm 3an K wbym 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 macaw bmbon was by a 0mm 5 L4memmA 3an K wbym El 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 7 Suppose e does not belong to T 7 Adding e to T creates a cycle C in 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 in both 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 5 14mm 3an K wbym g 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 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 3 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 W s Rasldwahtlwvm baman sum by E 0mm G 1mm A min K wbym

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.