### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Data Structures and Algorithms CSCE 3110

UNT

GPA 3.7

### View Full Document

## 73

## 0

## Popular in Course

## Popular in ComputerScienence

This 11 page Class Notes was uploaded by Joshuah McLaughlin on Sunday October 25, 2015. The Class Notes belongs to CSCE 3110 at University of North Texas taught by Philip Sweany in Fall. Since its upload, it has received 73 views. For similar materials see /class/229102/csce-3110-university-of-north-texas in ComputerScienence at University of North Texas.

## Popular in ComputerScienence

## Reviews for Data Structures and Algorithms

### 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: 10/25/15

Minimum Spanning Tree Reference Chapter 20AlgoriThms in Java 3rd Edition Robert Sedgewick Ruben Sedgewick and Kevin Wayne Cupyrighl s 2005 we wvvarmcelun EDUNcu5226 Minimum Spanning Tree MST Given connecTed graph G wiTh posiTive edge weighTs find a min weighT seT of edges ThaT connecTs all of The verTices 4rOf 24 6 23 g Y IE 16 5 K 1 4 7 cosTT 50 Theorem Cayley1889 There are W 2 spanning Trees on The compleTe graph on V verTices can l solve by brute force Minimum Spanning Tree MST Given connecTed graph G wiTh posiTive edge weighTs find a min weighT seT of edges ThaT connecTs all of The verTices O 24 7 4 23 h 9 1E lb 5 11 Clt a 7 1o 14 21 G MST Origin OTakar BorLIvka 1926 ElecTrical Power Company of WesTern Moravia in Brno MosT economical consTrLIcTion of elecTrical power neTwork ConcreTe engineering problem is now a cornersTone problem in combinaTorial opTimizaTion i OTakar Boruvka ApplicaTions Medical Image Processing MST is fundamenTal problem wiTh diverse applicaTions MST describes arrangement of nuclei m m epithelium for cancer research NeTwork desi n 9 Telephone elecTrical hydraulic TV cable compuTer road ApproximaTion algoriThms for NPhard problems Traveling salesperson problem STeiner Tree IndirecT applicaTions max boTTleneck paThs LDPC codes for error correcT39on image regisTraTion wiTh Renyi enTropy learning salienT feaTures for realTime face verificaTion reducing daTa sTorage in sequencing amino acids in a proTein model localiTy of parTicle inTeracTions in TurbulenT fluid flows auToconfig proTocol for ETherneT bridging To avoid cycles in a neTwork ClusTer analysis mp WW lch Weimummiimi mmi Two Greedy A lgoriThms Kruskal39s algoriThm Consider edges in ascending order of cosT Add The nexT edge To T unless doing so would creaTe a cycle Welg Gr39Op hs Prim39s algoriTh m STarT wiTh any verTex s and greedin grow a Tree T from 5 AT each sTep add The cheapesT edge To T ThaT has exachy one endpoinT in T Theorem BoTh greedy algoriThms compuTe an MST Greed is good Greed is righT Greed works Greed clarifies cuTs Through and capTures The essence of The evoluTionary spiriT quot Gordon Gecko Ruben Sedgewick and Kevin Wayne Cupyrigm 9 2005 hilp wwarincelun EbUNcu5226 Weigh red Graph In rem ace Return Type Method Action WeightedGzaph int V create empty graph void insert Edge 9 add edge e ItezableltEdgegt adj int v return iterator over edges incident to v int v0 return number of vertices String toStzingO return string representation for int v o v lt Gv v for Edge e Gadjv int w eotherv edge v w iterate through 0 edges me n each dv zc on Weigh red Graph Java Implemen ra rion Iden rical To Graph java bLIT use Edge adjacency lisTs ins read of int public class WeightedGraph private int v if vertices private SequenceltEdgegt adj adjacency lists public Graphint v t39 v adj new SequenceltEdgegt Sequencev for int v o v lt v v jv new SequenceltEdgegt public void insertEdge e int v ev w ew adj v adde adj w adde public Iterab1eltEdgegt adjint v return adj v Ruben Sedgewrk and Kevm Wayne Cupymgm e 2005 Edge Da ra Type public class Edge implements Comparab1eltEdgegt public final int v int w public final double weight public Edgeint v int w double weight thisv v thisw W thisweight weight public int ctherint vertex if vertex v return w else return v public int compareToEdge f Edge e his if ew eight lt fweight return 1 else if eweight gt fweight return 1 else return MST S rr39uc rur39e nnp WWN Prmcemn EbUNcu5226 Spanning Tree MST Given connecTed graph G wiTh posiTive edge weighTs find a min weighT seT of edges ThaT connecTs all of The verTices Def A spanning Tree of a graph G is a subgraph T ThaT is connecTed and acyclic ProperTy MST of G is always a spanning Tree CuT ProperTy Simplifying assumpTion All edge cosTs c2 are disTincT CuT properTy LeT S be any subseT of verTices and leT e be The min cosT edge wiTh exachy one endpoinT in S Then The MST T conTains e Pf by conTradicTion Suppose e does noT belong To T LeT39s see whaT happens Adding e To T creaTes a unique cycle C in T Some oTher edge in C say f has exachy one endpoinT in S T T U e f is also a spanning Tree Since c2 lt cf cosTT lt cosTT This is a conTradicTion Greedy AlgoriThms Simplifying assumpTion All edge cosTs c2 are disTincT Cycle properTy LeT C be any cycle and leT f be The max cosT edge belonging To C Then The MST does noT conTain f CuT properTy LeT S be any subseT of verTices and leT e be The min cosT edge wiTh exachy one endpoinT in S Then The MST conTains e f is noT in The MST e is in The MST Cycle ProperTy Simplifying assumpTion All edge cosTs c2 are disTincT Cycle properTy LeT C be any cycle in G and leT f be The max cosT edge belonging To C Then The MST T does noT conTain f Pf by conTradicTion Suppose f belongs To T LeT39s see whaT happens DeleTing f from T disconnecTs T LeT S be one side of The cuT Some oTher edge in C say e has exachy one endpoinT in S T T U e f is also a spanning Tree Since c2 lt cf cosTT lt cosTT This is a conTradicTion Kruskal39s AlgoriThm Ruben Sedgewick and Kevin Wayne Cupyrighl s 2005 hllp wwarmcelun EDUNcu5226 Kruskal39s AlgoriThm Example I s H 1 f i I 399 239quot a o a 0 t 3 s 1 MA 39 quot L in 75 s I 139 4 100 Kruskal39s AlgoriThm Example Kruskal39s algoriThm Kruskal 1956 Consider edges in ascending order of cosT Add The nexT edge To T unless doing so would creaTe a cycle M g 375 177 0amp6 o e o o 0 9 0 Kruskal39s AlgoriThrn Proof of CorrecTness Theorem Kruskal39s algoriThm compLITes The MST Pf case 1 If adding e To T creaTes a cycle C Then e is The max weighT edge in C so The cycle properTy asserTs ThaT e is noT in The MST Kruskal39s AlgoriThm Proof of CorrecTness Theorem KrLIskal39s algoriThm compLITes The MST Pf case 2 If adding e V w To T does noT creaTe a cycle Then e is The min weighT edge wiTh exachy one endpoinT in 5 so The cLIT properTy asserTs ThaT e is in The MST set ufverlices n v s connected componem Kruskal39s AlgoriThm ImplemenTaTion Q How To check if adding an edge To T would creaTe a cycle A2 Use The unionfind daTa sTrLIcTLIre MainTain a seT for each connecTed componenT If v and w are in same componenT Then adding vw creaTes a cycle To add vw To T merge seTs conTaining v and w Case l add ng rw creates a cycle Case 2 add vrw m T and merge sets KrLIskal39s AlgoriThm ImplemenTaTion Q How To check if adding an edge To T would creaTe a cycle A1 Naive solLITion use DFS OV Time per cycle check OE V Time overall KrLIskal39s AlgoriThm Java ImplemenTaTion public class Kruskal private SequenceltEdgegt mst new SequenceltEdgegt public Kruska1WeightedGraph G sort edges in ascending order Edge edges Gedges Arrays sortedges greedily add edges to MST UnionFlnd uf new UnionFindGV amp mstsize lt Gv 1i x n w edgesi 14 if luffindv w ufunitev w mstaddedges 1 safe m slap early if Tree already has vei edges public IterableltEdgegt mst return Inst Kruskal39s AlgoriThm Running Time KrLIskal running Time OE log V E S v2 so 0log E is Olog v i sort 1 union V 1 nd E E log V logquot V l logquot V l T amortized bound using weighted qu ck union will pain compression Remark If edges already sor red OE log V Time recall logv S 5 nihisumverse Prim39s Algori rhm Example Prim39s algori ihm Jarnik 1930 Dijksfra 1957 Prim 1959 STarT wiTh vertex 0 and greedily grow Tree T AT each sTep add cheapes i edge That has exactly one endpoint in T 0 9 0 r 4 i 4 o J l 1 T o Jquot l 1 91 on Prim39s Algori rhm Ruben Sedgewick and Kevin Wayne Cupyrigm s 2005 Nip wwarmcelun EDUNcu5226 Prim39s Algori rhm Example 3 gig v Prim39s AlgoriThm Proof of CorrecTness Prim39s AlgoriThm ImplemenTaTion Theorem Prim39s algoriThm compLITes The MST Q How To find cheapesT edge wiTh exachy one endpoinT in 5 PT LeT S be The subseT of verTices in currenT Tree T A1 BrLITe force Try all edges Prim adds The cheapesT edge e wiTh exachy one endpoinT in S OE Time per spanning Tree edge CLrT properTy asserTs ThaT e is in The MST OE V Time overall Prim39s AlgoriThm ImplemenTaTion Prim39s AlgoriThm Java ImplemenTaTion Q How To find cheapesT edge wiTh exachy one endpoinT in 5 public class LazyPrim rivate SequenceltEdgegt Inst new SequenceltEdgegt A2 MainTain edges wiTh aT leasT one endpoinT in Sin a prioriTy queue Public Lazyprimw ghtedsmph G W m 5 DeIeTe min To deTermine nexT edge e To add To T boolean marked new booleanGV Disregard e if boTh endpoinTs are in S MinPQltEdgegt pq new MinPQltEdgegt Upon adding e To T add edges incidenT To one endpoinT To PQ markedlo true add alledges ncidenHoO for Edge e Gadj0 pqinserte mg one not already in 5 RunningTIme while lpqisEmpty Ed d m disregardedgeifboln oaog V W per edge usingabmary heap 3 3 3129 OE log V Time overall if lmarkedv M if lmarkedv for Edge f if lmarkedw for Ed e f Gadjw markedv markedm t lmarkedw mstadde G39adjlvll Pq39insertlf lheseedgeshave exacllyone pqinsertf endpmm HS u Removing The DisTincT Edge CosTs AssumpTion Simplifying assumpTion All edge cosTs 2 are disTincT One way To remove assumpTion Kruskal and Prim only access edge weighTs ThroughT compareTo39 suffices To inTrodLIce Tiebreaking rLIle public int collipareToEdge f E ge is if eweight lt fweight return 1 if eweight gt fweight return 1 if ev lt fv if e v gt fv if 214 lt fw f ew gt fw return 0 return 1 Advanced MST AlgoriThms Ruben Sedgewick and Kevin Wayne CupyrigthZOOE thwwarmcelunEDUNcu5226 Removing The DisTincT Edge CosTs AssumpTion Simplifying assumpTion All edge cosTs 2 are disTincT FacT Prim and Kruskal don39T ClCl LlCllly rely on The assumpTion only our proof of correcmess doesl Advanced MST A lgoriThms 1975 E log log v Yao 1976 E log log v CheriTonTarjan 1984 E log v E v log v 1986 E log on v FredmanTarjan GabowGali lSpencerTarjan 1997 E uV log 1V Chazelle 2000 E uV Chazelle 2002 optimal PettieRamachandran 20 E 7 delermmisl c comparison based MST aigonnnns E 1976 Planar MST CheriTonTarjan 1992 MST Verification E 1995 Randomized MST E DixonRauchTarjan KargerKleinTarjan related problems Euchdean MST Euchdean MST Euchdea v MST em N Wm m me We nd MST cannec mg mm Keygeame ncfac Edge mm Euchdea v MST are 2192 w m Dmance between pmm paw m2 Euchdea vdma vce D2 aunay Hangu a mquot Euc man MST a gm w m Campm Varanm magnum mge D2 aunayhmngu mmn Run mm MST a gmwhm an D2 aunay 2192 Runmng me owagm ram xiN Demmayedgemcew xwanm E z z ow ag mm mm Erumfmce Campme mamam and run mm a gmwhm WWW mm geamehya vd da w m ow ag N Lawer haund Anycampanxanrhmed mumquot Msr a gamhm reqmm gm ag N campanian C usvermg ngering mm 6W mm ammmmm WP WW mmquot mm W mch w m mm mmWwMWM quotm 4 MammeA Fundamemal pmh em wag mac ux er mm pmm mmfferem c ux erxarzfmap n mm mam q r Idermfypaner g Bexpreiimn mm nwmrmm Dacumem c mgmm mquot my web 20 Sxm arwy Searchmg m mam wage mm 5ka mm mvgmmm mm quaxars ga axm mmnw quotwm u iwm ClusTering of Maximum Spacing kcusTering Divide objecTs inTo k nonempTy groups DisTance funcTion Assume iT saTisfies several naTuraI properTies cv w 0 iff v w idenTiTy of indiscernibles cv w 2 O nonnegaTiviTy cv w cw v symmeTry Spacing Min disTance beTween any pair of poinTs in differenT cusTers CIusTering of maximum spacing Given an inTeger k find a kcusTering of maximum spacing Dendrogram Dendrogram ScienTific visualizaTion of hypoTheTicaI sequence of evoluTionary evenTs Leaves genes InTernaI nodes hypoTheTicaI ancesTors mumi clmiel J euice scaia lem eneplcien iiiitaiic Reference th WWN biusmr WiSC edubmi57 faii72003i2crur213pdf Single Link ClusTering AlgoriThm Singlelink kcusTering algoriThm Form V cusTers of one objecT each Find The cosesT pair of objecTs such ThaT each objecT is in a differenT cusTer and add an edge beTween Them RepeaT unTiI There are exacTIy k cusTers ObservaTion This procedure is precisely Kruskal39s algoriThm excepT we sTop when There are k connecTed componenTs ProperTy AlgoriThm finds a kcusTering of maximum spacing Dendrograrn of Cancers in Human Tumors in similar Tissues cusTer TogeTher Gene 1 Gene n Skin lezl Lung Evunmmuu e mum Brain ADL mm Lhmlnal I gene expressed Reference Bursrein ABruwn group I gene m expressed

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