### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 715 Note 10 for CSE 565 at PSU

### View Full Document

## 20

## 0

## Popular in Course

## Popular in Department

This 12 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 20 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 715 Note 10 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

Algerithm Design and Analysis LECTURE 10 Implementing MST Algorithms Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 9152008 Minimum spanning tree MST Input A connected undirected graph G V E with weight function w E a R For now assume all edge weights are distinct Output A spanning tree T a tree that connects all vertices of minimum weight wT 2wuv WET 9152008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne 2 Greedy Algorithms for MST Kruskal39s Start with T 4 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 disconnect T Prim39s Start with some root node s Grow a tree T from s outward At each step add to T the cheapest edge e with exactly one endpoint in T 9152008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne 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 e is in The MST f is not in The MST 9152008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Prim39s algorithm Jarnik 1930 Prim 1959 Initialize S any node Apply cut property to S When edge weights are distinct the edge that is added must be in the MST Thus Prim s alg outputs the MST 9152008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne KruskaL 1956 Consider edges in ascending order of weight Case 1 If adding e to T creates a cycle discard e according to cycle property Case 2 Otherwise insert e u V into T according to cut property Where S set of nodes in u39s connected component 9152008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Nondistinct edges 9152008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Implementation of PrimGW IDEA Maintain V S as a priority queue Q as in Dijkstra Key each vertex in Q with the weight of the least geight edge connecting it to a vertex in S keyv e 00 for all v E V keys e 0 for some arbitrary s E V While Q Q do u e EXTRACTMINQ for each v E AayacencyZis u do if v E Q and wu v lt keyv then keyv e wu v gt DECREASEKEY rcv e u At the end 12 rcv forms the MST 9152008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Analysis of Prim Q 6 V 907 keyv e co for all v e V total keys e 0 for some arbitrary s E V f while Q Q do u e EXTRACTMINQ n for each 12 E Adj u timeslt 0768764 do if v E Q and wu v lt keyv times then keyv e wu v k rcv e u I Handshaking Lemma gt m implicit DECREASEKEY S Time as in Dijkstra 9152008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Analysis of Prim r While Q Q do u e EXTRACTMINQ n for each v E Adj u timeslt degreeu do if v E Q and wu v lt keyv times then keyv e wu v k rlv e u Handshaking Lemma gt m implicit DECREASEKEY S PQ Opera rion Binary heap dway Heap Fib heap r log n HW3 log n n 1 qu n HW3 1 Toi39ali n2 m log n m log N n39 m n log n 139 Individual ops are amor I ized bounds 9152008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Greedy Algorithms for MST Kruskal39s Start with T 4 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 disconnect T Prim39s Start with some root node s Grow a tree T from s outward At each step add to T the cheapest edge e with exactly one endpoint in T 9152008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Operation Implementation Array linkedlists and UnionFind Data Structures Balanced Trees sizes and k nds starting from singletons Find worstcase 91 9log 11 Union of sets AB GminAB could be as 9log n worstcase large as 9n Amortized analysis k unions 6k log k 6k log k With modifications amortized time for tree structure is On Ackn where Ackn the Ackerman function grows much more slowly than log n See KT Chapter 46 9152008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne

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

#### "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."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "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!"

#### "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.