### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 619 Note 9 for CSE 565 at PSU

### View Full Document

## 24

## 0

## Popular in Course

## Popular in Department

This 7 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 24 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 619 Note 9 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 9 Greedy Algorithms Minimum Spanning Tree Kruskal s Prim s ReverseDelete Clustering Sofya Raskhodnikova 7quot s Rarkmambwa baredonrluier byE Demamt c uuerramA 5mm K mm m m Minimum spanning tree MST Input A connected undirected graph G V E with weight function w E gt R For now assume all edge weights are distinct Output A spanning tree T i a tree that connects all vertices i of minimum weight wT Zwuv mgr mm s mmmnm baredonrluiaby a 0mm c mamas 5mm K mm g Greedy Algorithms for MST Kruskal39s Start with T o 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 wch step add to T the chapest edge e with exactly one endpoint in T mm s Kmmmnw baredonrluier byE Demamt c mamas 5mm K mm gl 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 c f 5 E ersmthe MST frsnutmthe MST mm s wmmhm baredonrldaby a Dmmt c mamas 5mm K mm m m Revrew Questions Let G be a connected undirected graph with distinct edge weights Answer true or false Let e be the cheapest edge in G Some MST of G contains e Let e be the most expensive edge in G No MST of G contains e 7quot s Rarkhoahtb m baredonrluier byE Demamt c mamas 5mm K mm W m Revrew Questions Let G be a connected undirected graph with distinct edge weights Answer true or false Let e be the cheapest edge in G Some MST of G contains e AnswerzYes by the Cut Property Let e be the most expensive edge in G No MST of G contains e Answer False Counterexample if G is a tree all its edges are in the MST 7 s mmmnm mmmwby a Dmmt c mamas 5mm K mm I Prim39s Algorithm Correctness Prim39s algorithm Jarni k 1930 Prim 1959 Elnitialize S any node EApply cut property to S EAdd to T min cost edge and add one new explored node 11 to S Wm s Railhombm baredovirlui byE Demamt c mama 5mm K mm I Demo of Prim s algorithm mm s Kammma baredovirlui byE Demamt c 1mm 5mm K mm Demo of Prim s algorithm Wm s Railhombm baredovirlui byE Demamt c 1mm 5mm K mm m l Implementation of PrimGw IDEA Maintain V E S as a priority queue Q ala Dijkstra Key each vertex in Q with the Weight of the last Weight edge connecting it to a vertex in S Q e V keyv e w for all v E V kEyLV e 0 for some arbitrary r E V while Q 9 do u e EXTRACTVMIMQ for eachv E Adjacencyrlir u do ifv E Q and Wm v lt keyv then keyv e wu v gt DECREASEKEY 1tv e 14 At the end v TLV forms the MST Wm s mmmkm mmmwby a Dmmt c AlreKDYAA 5mm K mm gl Demo of Prim s algorithm Yummy s wmmkowz baredonrluiaby a Dmmt c 1mm 5mm K mm gl Demo of Prim s algorithm Wm s mmmkm baredonrluiaby a Dmmt c 1mm 5mm K mm 7quot s nammbm baredonxlui a by Demamt c mama 5mm K mm mm s mmmnm mmmmmy a 0mm c meme 5mm K mm Demo of Prim s algorithm mm s RMUwahlhwd bandwile by 04th c mama 5mm 1c mm g Demo of Prim s algorithm 065 oeVis mm s wmahkom bluedonxluiaby a Dmmt c 1mm 5mm 1c mm I Demo of Prim s algorithm oeS 6 em 7quot s Rammbm bandwile by 04th c mama 5mm 1c mm g Demo of Prim s algorithm 7 s Rummkom bluedonxlmiby a Dmmt c 1mm 5mm 1c mm Demo of Prim s algorithm 7quot s RMUIOEMWWU baredonxlui a by Demamt c uuerxamA 5mm K mm Demo of Prim s algorithm QeS eViS mm s mmmkm bluedonxlmiby a 0mm c imam 5mm K mm Demo of Prim s algorithm mm s RMUwahlhwd bandwile by 04th c uuerxamA 5mm 1c mm gl Analysis of Prim Q lt V 80 keyv lt Do for all v e V mtal keys lt O for some arbitrary S e V While Q Q do u e EXTRACTMINQ for wch v e Adju n times 3734 dDif v 6 Q and wu v lt keyv mes then keyv ewm v 7Lv lt u Handshaking Lemma gt m implicit DECREASEKEY s Time as in Dijkstra mm s mmmkom baredonxluiaby a Dmmt c imam 5mm 1c mm Analysis of Prim While Q Q do u e EXTRACTMINQ for wch v e Adju n times degreeu do if v 6 Q and wu v lt keyv times then keyv 9 Wm V 7Lv lt u Handshaking Lemma 3 m implicit DECREASEKEY s WW 5 Ammonium bandwile by 04th c uuerxamA 5mm 1c mm M l Correctness of Kruskal KruskaL 1956 Consider edges in ascending order of Weight 7 Case 1 If adding e to T creates a cycle discard e according to cycle property Cased 7 Case 2 Othenxxise insert e u v into T according to cut property Where S set of nodes in Us connected compon ent Case 2 7 s Rummkom baredonxluiaby a Dmmt c imam 5mm 1c mm m Implementation of Kruskal Use the UnionFind data structure 7 Build set T of edges in the MST 7 Maintain a set for each connected component KiuskaJtG m t Sort edges weights so that quota s quot2 s um 1 v 0 foxeacn u s v make a set contaJang smgieton u mmm m 1W 351331 21123quot go through edges in sorted omer Jf u and v are An afferent sets m 4 r u en merge the sets ContaJang u and v mm I mngummpeme 7quot s RMUwahtbm baredonxluieer byE oemme c Lemme 5mm Lt Wayne am The UnionFind Data Structure Operations MAKEUNIONFINDS creates the data structure puts all elements in S into separate sets On time Where nS FlNDu returns the representative of the set containing u Olog n time UNIONAB merge sets AB into a single set 01 time mm s mmmam mmmmexby 5 Banana c Lemme 5mm Lt mm gl Linked List Representation For wch set keep the size the had the tail of the list 7 for each element keep a pointer to the representative head g MAKEUNIONFIND 01 time per element FINDX return a pointer to representative 01 time mm s Rarkhombva bandwile byE oemme c Lemme 5mm Lt Wayne gl Linked List Representation UNIONAB keep the representative of the larger set E m an mm s mmmhm mmmmexby a name c Lemme 5mm Lt mm Linked List Representation UNIONAB keep the representative of the larger set Excluding updates to representatives 01 time 7quot s Rarkhombva bandwile byE oemme c Lemme 5mm Lt Wayne g Analysis of UnionFind Theorem A sequence ofk UNION operations takes Ok log k time Proof We bound the number of updates to representatives Initially n singleton sets are created One UNION merges at most two of the singletons After k UNIONs all but 2k singletons are untouched At every UNION representativex is updamd only if the size of X s set at least doubles After k UNIONs x is in the set of size 3 2k Representativex is updamd S log2 2k times At most 2k elements are touched by k UNIONs Total time on updating representatives Ok log k 7 s mmmkm mmmmexby a name c Lemme 5mm Lt mm am Forest Representation Each element is a node Each tree represents one set store its size The root is the representative MAKEUNIONFIND create roots 7 01 time per element a UNIONAB point the root of the m e 0 smaller tree to the root of the larger tree 7 01 time I3 7quot s RMUwahibm bluedonrluieer byE 04mm c Lemme 5mm K Wayne m m FIND operation F1NDX follow the links to the root 0 Theorem FIND takes Olog n time a a Proof Time to evaluate FINDx 0 number of predecessors ofx 0 0 number of times x changes representatives Every time x changes representatives the size of its set at last doubles It mn happen g logZ n times mm s mammal bluedomluiexby 5 Banana c Lemme 5mm K mm g An Improvement to FIND Path Compression update every pointer on the way to the root 9 e FINDX 0 3o 49 o o o o a o Theorem n FIND operations take 0n un time Where an is inverse Ackerman function mm s RMUwathvd bluedonrluieer byE Demamt c Lemme 5mm K Wayne Implementation of Kruskal Build set T of edges in the MST Maintain a set for each connected component Kmskairq m lt Son edges weights so that w s was g 394quot T v mmw mammno v foreech edge uv go through edges in sorted omer Jf FINDNJ u mom lt 139 o r u an Unromrmmu mums gt return 1 m U ml V m Wm cam cud campamms mg m comm l Sorting 0m log m 0m log n2 0m log n Union7Find operations 0m log n 0m10g H mm mm s mmmhw baredonrlderby a name c Lemme 5mm K mm m LeXicographic Tiebreaking To remove the assumption that all edge costs are distinct perturb all edge costs by tiny amounts to break any ties i g M all ag casts m Mingus pnng cast a ag by m n Impact Kruskal and Prim only interact with costs via pairwise comparisons If perturbations are sufficiently small MST with perturbed costs is MST with original costs Implementation Can handle arbitrarily small perturbations implicitly by braking ties lexicographically according to index 7quot s RMUWHMWWE bluedonrluieer byE Demamt c Lemme 5mm K Wayne g MST Algorithms in 2007 Deterministic comparison based algorithms 70m log n J arni k Prim Dijkstra Kruskal Boruvka 7 0m or m n Chazelle 2000 Holy grail 0rn Related 7 0m randomized KargerKleinTarjan 1995 7 0m veri cation DixonRauchTarjan 1992 7 s M wmikow mmmmexby a name c Lemme 5mm K mm I Clustering I Clustering Given a set U of 11 objects eg photos documents microorganizms labeled p1 pn classify them into coherent groups Distance function for each pair of objects Close number of corresponding pixels whose inTensiTies differ by some Threshold Fundamental problem Divide into clusters so that objects in different clusters are far apart Routing in mobile ad hoc networks Identify patterns in gene expression Document categorization for web search Similarity searching in medical image databases Skycat cluster 109 sky objects into stars quasars galaxies Ou rbreak of cholera deaThs in London in 1850s Reference Nina Mishra UniversiTy of Virginia 9172007 9172007 S Raskhodnikova based on slides by E Demaine C Leiserson A Smith K Wayne S Raskhodnikova based on slides by E Demaine C Leiserson A Smith K Wayne Clustering of Maximum Spacing I Greedy Clustering Algorithm 0kclustering Divide objects into k non empty groups Singlelink kclustering algorithm 0Distance function satisfies Form a graph on the vertex set U corresponding to 11 clusters dpi pj iff pi pj identity of indiscamiblas Find the closest pair of objects such that each object is in a different cluster and add an edge between them dpi pj 2 0 nonnegat1v1ty 39 Re eat n k times until there are exactl k clusters dpi pj dpj pi symmetry y P y 39 spacmg o o Spacmg Mlmmum dlstanca batwean Keyoobservatlon ThIS procedure is prec1sely Kruskal s u algorithm except we stop when there are k connected any pair of pomts in different clusters 39 9 components OGoal Given an inte er k find g Remark Equivalent to finding an MST and deleting the a k clustermg of max1mum spacmg k 4 k1 most Expensive EdgES 9172007 S Raskhodnikova based on slides by E Demaine C Leiserson A Smith K Wayne 9172007 S Raskhodnikova based on slides by E Demaine C Leiserson A Smith K Wayne Theorem Let C be the clustering C1 Ck formed by deleting k 1 most expensive edges of a MST C is a k clustering of max spacing Proof Let C be some other clustering C1 Ck The spacing of CgtXlt is the length dgtXlt of klSt most expensive edge Let pi p be in the same cluster in C say Ci but different clusters in C say CS and Ct C Some edge p q on pipj path in Cgtlltr CS spans two different clusters in C C i All edges on pipj path have length S dgtXlt Il since Kruskal chose them Spacing of C is S dgtXlt since p and q I are in different clusters I 9172007 S Raskhodnikova based on slides by E Demaine C Leiserson A Smith 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

#### "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 used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

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