### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Algorithms CS 673

USF

GPA 3.7

### View Full Document

## 25

## 0

## Popular in Course

## Popular in ComputerScienence

This 69 page Class Notes was uploaded by Michele Herzog on Thursday October 29, 2015. The Class Notes belongs to CS 673 at University of San Francisco taught by David Galles in Fall. Since its upload, it has received 25 views. For similar materials see /class/231236/cs-673-university-of-san-francisco in ComputerScienence at University of San Francisco.

## Reviews for 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/29/15

CS6732008F08 Extending Data Structures 080 Dynamic Order Statistics 0 Data structure with following operations 0 Insert Remove Find 9 lg n 0 Find nth smallest element 0 Find the rank of any element is it smallest second smallest etc How can we do this with redblack trees 0 How to nd the rank of any element in a redblack tree 0 How to nd the nth element in a redblack tree 081 Dynamic Order Statistics 0 Addinging functionality to redblack trees 0 Finding the nth element in a redblack tree 0 Finding the rank of any element in a redblack tree 0 What if we could add some other data to a redblack tree to make this easier 0 What should we add 0 How could we use it 082 Size Field 0 Add a size eld to each node in a redblack tree 0 How can we use this size eld to nd the nth element in the tree 0 How can we use this size eld to nd the rank of any element 0 Can we maintain the size eld and still have insertremove nd take time Olg n 083 Using Size Field 0 To nd the kth element in a redblack tree with size eld 0 If of elements in left subtree k 7 1 then root is the kth element 0 if of elements in left subtree gt k 7 1 then the kth element is the kth element in the left subtree o if of elements in the left subtree n lt k 7 1 then the kth element is the n 7 k 1th element in the right subtree 084 Updating Size Insert 0 Updating size eld on insert 085 Updating Size Insert 0 Updating size eld on insert 0 As we go down the tree looking for the correct place to insert an element add one to the size eld of every node along the path from the root to the inserted element 0 examples on board CS6732008F08 Extending Data Structures 086 Updating Size Delete 0 Updating size eld on delete 087 Updating Size Delete 0 Updating size eld on delete 0 As we go down the tree looking for the element to delete delete one from the size of evey node along the path from the root to the deleted element 0 examples on board 0 Need to be careful about trying to delete elements that aren t in the tree 088 Updating Size Field Rotate 0 Updating size on rotations o How should sizes be updated on rotations 0 Picture on board 089 Updating Size Field Rotate Right Rotate A 6 V A A Left Rotate Sizes of ABC not changed Sizes ofABC not changed SizeX SizeA SizeB SizeY SizeB SizeC SizeY SizeX SizeC SizeX SizeA SizeY 0810 Augmenting Data Structures 0 Decide what extra information to add to each element of the data structure 0 Make sure we can update this extra information for each operation on the data structure 0 Add operations that use this extra information 0 New operations 0 Do old operations more ef ciently Finding rank example 0811 Augmenting Data Structures 0 For RedBlack trees 0 If extra information in a node is dependent only on the node itself and values in left amp right children 0 Then we can always update this information during insert and delete in time Olg n CS6732008F 08 Extending Data Structures 0812 Augmenting Data Structures 0 On an insert 0 Add the leaf 0 Update information on path from leaf to root after the insertion 0 Extra time Olg n o Rotate as necessary 0813 Augmenting Data Structures 0 On a delete 0 Delete the node 0 Update information on path from deleted node to root after deletion is completed 0 also works for deletion of node w 2 children do example 0 Extra time Olg n o Rotate as necessary 0814 Augmenting Data Structures Right Rotate GE 0 Values in ABC don t need to change 0 Values in XY can be changed by looking at ABC 0 Might need to propagate change up the tree time Olg n 0815 Intervals 0 Closed intervals 0 239 t1 t2 0 All values between t1 and t2 including t1 and t2 0 Open HalfOpen intervals 0 239 t17t2i 7517752 o All values between t1 and t2 not including t1 or t o All values between t1 and t2 including it but not t1 0816 Intervals 0 Given two intervalsz39 tth and zquot it1 t Q CS6732008F 08 Extending Data Structures 0 Three cases 0 239 and zquot overlap including one is a subset of the other 0 239 is to the left of zquot o 239 is to the right if 2quot 0817 Intervals 0 Data structure that manipulates intervals 0 Insert a closed interval using endpoints 0 Delete a closed interval using endpoints 0 Find an interval 0 Given an interval 239 nd an interval that overlaps 239 o If gt 1 interval overlaps i return one arbitrarily 0818 Interval Trees 0 First Try 0 Each node stores lowhigh endpoint of interval 0 Sorted based on low endpoint o No extra information yet 0819 Interval Trees 36 01 1416 0820 Interval Trees 0 Data Structure 0 Each node stores lowhigh endpoint of interval 0 Sorted based on low endpoint 0 Extra information Maximum value of any interval stored in the subtree rooted at this node CS6732008F 08 Extending Data Structures 0821 Interval Trees 1 16 0 1 14 16 0822 Interval Trees 0 Extra Information 0 Maximum value of any interval stored in the subtree 0 Can we maintain this extra information through inserts and deletes 0823 Interval Trees 0 Extra Information 0 Maximum value of any interval stored in the subtree 0 Can we maintain this extra information through inserts and deletes 0 Yes Maximum value in a subtree only depends upon 0 High endpoint stored in current node 0 Maximum value in left subtree 0 Maximum value in right subtree Example updates on board 0824 Interval Trees 0 How do we nd an interval 0 Given an interval 239 nd an interval that overlaps 239 o If gt 1 interval overlaps i return any one of the intervals that overlap 239 examples in next slide 0825 Interval Trees CS6732008F 17 Shortest Path Algorithms 1 170 Computing Shortest Path 0 Given a directed weighted graph G all weights nonnegative and two vertices z and y nd the leastcost path from I to y in G o Undirected graph is a special case of a directed graph with symmetric edges 0 Leastcost path may not be the path containing the fewest edges 0 shortest path least cost path 0 path containing fewest edges path containing fewest edges 171 Shortest Path Example 0 Shortest path y path containing fewest edges 4 E 2 o Shortest Path from A to E 172 Shortest Path Example 0 Shortest path y path containing fewest edges wz o Shortest Path from A to E o A B C D E 173 Single Source Shortest Path CS6732008F 17 Shortest Path Algorithms 2 0 To nd the shortest path from vertex 1 to vertex y we need worst case to nd the shortest path from I to all other vertices in the graph 0 Why 174 Single Source Shortest Path 0 To nd the shortest path from vertex 1 to vertex y we need worst case to nd the shortest path from I to all other vertices in the grap 0 To nd the shortest path from I to y we need to nd the shortest path from I to all nodes on the path from I to y 0 Worst case all nodes will be on the path 175 Single Source Shortest Path 0 If all edges have unit weight 176 Single Source Shortest Path 0 If all edges have unit weight 0 We can use Breadth First Search to compute the shortest path 0 BFS Spanning Tree contains shortest path to each node in the graph 0 Need to do some more work to create amp save BFS spanning tree 0 When edges have differing weights this obviously will not work 177 Single Source Shortest Path 0 General Idea for nding Single Source Shortest Path 0 Start with the distance estimate to each node except the source as oo o Repeatedly relax distance estimate until you can relax no more 0 To relax and edge u7 v o distv gt distu costu7 v 0 Set distv lt7 distu costu7 v 178 Single Source Shortest Path 0 Dijkstra s algorithm 0 Relax edges from source 0 Remarkably similar to Prim s MST algorith 0 Pretty neat 7 algorithms are doing different things but code is almost identical 179 Single Source Shortest Path 0 Divide the vertices into two sets 0 Vertices whose shortest path from the initial vertex is known CS6732008F 17 Shortest Path Algorithms o Vertices whose shortest path from the initial vertex is not known 0 Initially only the initial vertex is known 0 Move vertices one at a time from the unknown set to the known set until all vertices are known 1710 Single Source Shortest Path 2 A B R 2 2 C D E F 4 G l 0 Start with the vertex A 1711 Single Source Shortest Path Node Distance B A 0 3 10 c 2 2 D C4 D D E E 5 8 6 F G F4 G 1 0 Known vertices are circled in red 0 We can now extend the known set by l vertex 1712 Single Source Shortest Path Node Distance CI39TJD39JUO CS6732008F 17 Shortest Path Algorithms 0 Why is it safe to add D with cost 1 1713 Single Source Shortest Path Node Distance B R E G 0 Why is it safe to add D with cost 1 0 Could we do better with a more roundabout path 1714 Single Source Shortest Path Node Distance 0 Why is it safe to add D with cost 1 0 Could we do better with a more roundabout path 0 No 7 to get to any other node will cost at least 1 o No negative edge weights can t do better than 1 1715 Single Source Shortest Path Node Distance 0 We can now add another vertex to our known list CS6732008F 17 Shortest Path Algorithms 1716 Single Source Shortest Path o How do we know that we could not get to B cheaper than by going through D 1717 Single Source Shortest Path o How do we know that we could not get to B cheaper than by going through D 0 Costs 1 to get to D 0 Costs at least 2 to get anywhere from D 0 Cost at least 12 3 to get to B through D 1718 Single Source Shortest Path Node Distance B 2 C D l E F G 0 Next node we can add CS6732008F 17 Shortest Path Algorithms 1719 Single Source Shortest Path Node Distance 2 C 3 D l E F G 0 We also could have added E for this step 0 Next vertex to add to Known 1720 Single Source Shortest Path Di st ance 2 3 l 3 0 Cost to add F is 8 through C 0 Cost to add G is 5 through D 1721 Single Source Shortest Path Di 5 tance U39IUJHUJN 0 Last node CS6732008F 17 Shortest Path Algorithms 1722 Single Source Shortest Path Distance OiU39IWl WNO 0 We now know the length of the shortest path from A to all other vertices in the graph 1723 Dijkstra s Algorithm 0 Keep a table that contains for each vertex 0 Is the distance to that vertex known 0 What is the best distance we ve found so far 0 Repeat 0 Pick the smallest unknown distance 0 mark it as known 0 update the distance of all unknown neighbors of that node 0 Until all vertices are known 1724 Dijkstra s Algorithm Example 1725 Dijkstra s Algorithm Example CS6732008F 17 Shortest Path Algorithms Distanc e 1726 Dijkstra s Algorithm Example Distanc e 1727 Dijkstra s Algorithm Example Distanc e 1728 Dijkstra s Algorithm Example CS6732008F 17 Shortest Path Algorithms Distanc e 1729 Dijkstra s Algorithm Example 1730 Dijkstra s Algorithm Example 1731 Dijkstra s Algorithm 0 After Dijkstra s algorithm is complete CS6732008F 17 Shortest Path Algorithms 10 0 We know the length of the shortest path 0 We do not know what the shortest path is o How can we modify Dijstra s algorithm to compute the path 1732 Dijkstra s Algorithm 0 After Dijkstra s algorithm is complete 0 We know the length of the shortest path 0 We do not know what the shortest path is o How can we modify Dijstra s algorithm to compute the path 0 Store not only the distance but the immediate parent that led to this distance 1733 Dijkstra s Algorithm Example A 5 gt E 2 c 14gt D 5 2 lt G F 1 1734 Dijkstra s Algorithm Example A 5 p E 2 c 14gt D 5 2 lt G F 1 1735 Dijkstra s Algorithm Example A 5 1 2 c 14gt D 5 2 lt G F 1 CS6732008F 17 Shortest Path Algorithms 1736 Dijkstra s Algorithm Example 5 1737 Dijkstra s Algorithm Example 1738 Dijkstra s Algorithm Example 5 1739 Dijkstra s Algorithm Example 1740 Dijkstra s Algorithm Example CS6732008F 17 Shortest Path Algorithms 1741 Dijkstra s Algorithm 0 Given the path eld we can construct the shortest path 0 Work backward from the end of the path 0 Follow the path pointers until the start node is reached 0 We can use a sentinel value in the pat eld of the initial node so we know when to stop 1742 Dijkstra Code Void DjkstraEdge cu m s tablemtry m w mow Ks length m Tm aism Ce IntegermleivALUE Tm pach 71 1 1 3156 1eenexe or stance gt 1 came e 7 Tmmsmce Hm h V 1743 Dijkstra Running Time 0 If minUnknoanertexT is calculated by doing a linear search through the table 0 Each minUnknoanertex call takes time GO V o Called V times 7 total time for all calls to minUnkoanertex GO VP 0 If statement is executed times each time takes time 01 0 Totaltime OOVP OOVP 1744 Dijkstra Running Time 0 If minUnknoanertexT is calculated by inserting all vertices into a minheap using distances as key updating the heap as the distances are changed 0 Each minUnknoanertex call tatkes time Glg o Called V times 7 total time for all calls to minUnknoanertex GO V lg o If statement is executed times 7 each time takes time OOg V keys in heap since we need to update decrement CS6732008F 17 Shortest Path Algorithms 13 o Totaltime OV lg V lg V E lg 1745 Dijkstra Running Time 0 If minUnknoanertexT is calculated by inserting all vertices into a Fibonacci heap using distances as key updating the heap as the distances are changed 0 Each minUnknoanertex call takes amortized time lg V o Called V times 7 total amortized time for all calls to minUnknoanertex GO V lg o If statement is executed times 7 each time takes amortized time 01 since decrementing keys takes time 0 o Totaltime OV lgV 1746 Negative Edges 0 Does Dijkstra s algorithm work when edge costs can be negative 0 Give a counterexample o What happens if there is a negativeweight cycle in the graph 1747 BellmanFord o Bellm anFord allows us to calculate shortest paths in graphs with negative edge weights as long as there are no negativeweight cycles 0 As a bonus we will also be able to detect negativeweight cycles 1748 BellmanFord o For each node v maintiain o A distance estimate from source to v dv 0 Parent of v v that gives this distance estimate 0 Start with dv 00 v nil for all nodes 0 Setdsource 0 o udpate estimates by relaxing edges 1749 BellmanFord o Relaxing an edge u7 v 0 See if we can get a better distance estimate for v by going thorugh u Relaxuvw if dv gt du wuv dv du 111u7 v u lt7 u 1750 BellmanFord CS6732008F 17 Shortest Path Algorithms 14 o Relax all edges edges in the graph in any order 0 Repeat until relax steps cause no change 0 After rst relaxing all optimal paths from source of length l are computed 0 After second relaxing all optimal paths from source of length 2 are computed 0 after V 7 1 relaxing all optimal paths of length V 7 1 are computed o If some path of length V is cheaper than a path of length V 7 1 that means 1751 BellmanFord o Relax all edges edges in the graph in any order 0 Repeat until relax steps cause no change 0 After rst relaxing all optimal paths from source of length l are computed 0 After second relaxing all optimal paths from source of length 2 are computed 0 after V 7 1 relaxing all optimal paths of length V 7 1 are computed o If some path of length V is cheaper than a path of length V 7 1 that means 0 Negative weight cycle 1752 BellmanFord Bellam anFordG7 s Initialize 7r forilt71toV 71do for each edge u7 v E G do ifdv gt du wuv dv lt7 du wuv 7r 1 lt7 u for each edge u7 v E G do if dv gt du wu7 1 return false return true 1753 BellmanFord 0 Running time 0 Each iteration requires us to relax all E edges 0 Each single relaxation takes time 01 0 V 7 1 iterations V if we are checking for negative weight cycles 0 Total running time OV 17 54 Shortest PathDAGs 0 Finding Single Source Shorest path in a Directed Acyclic graph 0 Very easy How can we do this quickly 17 55 Shortest PathDAGs CS6732008F 17 Shortest Path Algorithms 15 0 Finding Single Source Shorest path in a Directed Acyclic graph 0 Very easy 0 How can we do this quickly 0 Do a topological sort 0 Relax edges in topological order 0 We re done 1756 AllSource Shortest Path 0 What if we want to nd the shortest path from all vertices to all other vertices o How can we do it 1757 AllSource Shortest Path 0 What if we want to nd the shortest path from all vertices to all other vertices o How can we do it 0 Run Dijktra s Algorithm V times 0 How long will this take 1758 AllSource Shortest Path 0 What if we want to nd the shortest path from all vertices to all other vertices o How can we do it 0 Run Dijktra s Algorithm V times 0 How long will this take 0 V2 lg V using Fibonacci heaps 0 Doesn t work if there are negative edges Running BellmanFord V times which does work with negative edges takes time 0V2E 7 which is V4 for dense graphs 1759 MultiSource Shortest Path 0 Let Um 2397 j in text lg be cost of the shortest path from 239 to j that contains at most m edges 0 Ifm 0 there is a shortest path from itoj with no edges iffz39 j Wm 0 ifz j 00 otherw1se o How can we calculate Lmi7 j recursively 1760 MultiSource Shortest Path 0 Let Um 2397 j in text lg be cost of the shortest path from 239 to j that contains at most m edges 0 ifz39 j L0Z7 00 otherwise CS6732008F 17 Shortest Path Algorithms 16 o How can we calculate Lmi7 j recursively WM min Lltm1gtijlrlt1gg ltLltm1gtik1wkjgt mm V lggn 27 k wch 1761 MultiSource Shortest Path 0 Create Um from Um ExtendShortest PathsL7 W n lt7 rowsL L lt7 new n X n matrix for 239 lt7 1 to n do for j lt7 1 to n do my 139 e co for k lt7 1 to n do mm H minltLtzijLtzy 1 WM return L 1762 MultiSource Shortest Path 0 Need to calculate L014 0 Why LOLA and not H or Mn AllPairsShortestPathsW n lt7 rowsW LO lt7 W formlt72ton71do Um lt7ExtendShortestPathLm l7 W return LOLA 1763 MultiSource Shortest Path 0 We really don t care about any of the L matrices except LOLA 0 We can save some time by not calculating all of the intermediate matrices L0 r r r L 2 0 Note that Extend ShortestPath looks a lot like matrix multiplication 1764 MultiSource Shortest Path SquareMatrixMultiplyA7 B n 7 rows C lt7 new n X n matrix forz39 lt7 1 to n o for j lt7 1 to n do Ci7 lt7 0 for k lt7 1 to n do Gilli H Cim Aim BUW39D return L CS6732008F 17 Shortest Path Algorithms 17 0 Replace min with 4r with 6 1765 MultiSource Shortest Path 0 Using our ExtendMultiplication 0 Replace with min 6 with L1L W W L1L1W W2 L2L2W W3 L3L3W W4 Loki Ln72 W Wnil 1766 MultiSource Shortest Path Llt1gt W Llt2gt W2 Llt4gt W4 U8 W8 Lyman 7 Lgngwm WW W2 FW2 W4 FW4 LgrlgwmA Lymwoul 0 Since LW I U L01 Hi it doesn t matter if n is an exact power of 2 7 we just need to get to at least L014 not hit it exactly 1767 MultiSource Shortest Path AllPairsShortestPathsW n lt7 rowsW LO lt7 W m lt7 1 Whilemlt nildo Lam lt7ExtendShortestPathLm7 Lm m A m 6 2 return Um 1768 MultiSource Shortest Path 0 Each call to ExtendShortestPath takes time o of calls to ExtendShortest Path 0 Total time CS6732008F 17 Shortest Path Algorithms 18 1769 MultiSource Shortest Path 0 Each call to ExtendShortestPath takes time GO V 3 o of calls to ExtendShortest Path lg V o Totaltime V31gV 1770 Floyd s Algorithm 0 Alternate solution to all pairs shortest path 0 Yields VS running time for all graphs 17 7 1 Floyd s Algorithm 0 Vertices numbered from On 0 kpath from vertex v to vertex u is a path Whose intermediate vertices other than 1 and u contain only vertices numbered k or less 0 0path is a direct link 1772 k path Examples o Shortest 0path from 1 to 5 5 o Shortest lpath from 1 to 5 5 o Shortest 2path from 1 to 5 4 o Shortest 3path from 1 to 5 4 o Shortest 4path from 1 to 5 3 1773 k path Examples 2 1 4 5 3 1 5 i1 5 1 o Shortest 0path from 1 to 3 7 3 CS6732008F17 Shortest Path Algorithms 19 o Shortest lpath from 1 to 3 7 o Shortest 2path from 1 to 3 6 o Shortest 3path from 1 to 3 6 o Shortest 4path from 1 to 3 6 o Shortest 5path from 1 to 3 4 1774 Floyd s Algorithm 0 Shortest n path Shortest path 0 Shortest 0path o 00 if there is no direct link 0 Cost of the direct link otherwise 1775 Floyd s Algorithm 0 Shortest n path Shortest path 0 Shortest 0path o 00 if there is no direct link 0 Cost of the direct link otherwise 0 If we could use the shortest kpath to nd the shortest k 1 path we would be set 1776 Floyd s Algorithm 0 Shortest kpath from v to u either goes through vertex k or it does not 0 If not 0 Shortest kpath shortest k 7 1path o If so 0 Shortest kpath shortest k 7 1 path from v to k followed by the shortest k 7 1 path from k to w 1777 Floyd s Algorithm 0 If we had the shortest kpath for all pairs vw we could obtain the shortest k 1path for all pairs 0 For each pair v7 w compare 0 length of the kpath from v to w 0 length of the kpath from v to k appended to the kpath from k to w 0 Set the k 1 path from v to w to be the minimum of the two paths above 1778 Floyd s Algorithm 0 Let Dk 1 w be the length of the shortest kpath from v to w 0 D0 1 w cost of arc from v to w 00 if no direct link CS6732008F17 Shortest Path Algorithms o Dkvw MNDk1vwDk1vk Dk1kw o Create Do use Do to create D1 use D1 to create D2 and so on 7 until we have Dn 1779 Floyd s Algorithm 0 Use a doublynested loop to create Dk from Dkil 0 Use the same array to store Dkil and Dk 7 just overwrite with the new values 0 Embed this loop in a loop from lk 1780 Floyd s Algorithm FloydEdge G int DH 1 int ijk Initialize D Dij cost from i to j for k0 kltGlength k fori0 iltGlength i forj0 jltGlength j if Di k IntegerMAXALUE ampamp Dk J IntegerMAXALUE ampamp Di j gt Dik Dkj Di j Di k Dk j 17 81 Floyd s Algorithm 0 We ve only calculated the distance of the shortest path not the path itself 0 We can use a similar strategy to the PATH eld for Dijkstra to store the path 0 We will need a 2D array to store the paths Pi last vertex on shortest path from i to j 1782 Johnson s Algorithm 0 Yet another allpairs shortest path algorithm 0 Time OOVPIngj jVj 6 o Ifgraph is dense 6 VP no better than Floyd 0 If graph is sparse better than Floyd 0 Basic Idea Run Dijkstra jVj times 0 Need to modify graph to remove negative edges 1783 Johnson s Algorithm 0 Reweighing Graph 0 Create a new weight function 12 such that o For all pairs of vertices u7 v E V a path from u to v is a shortest path using w if and only if it is also a shortest path using 12 CS6732008F 17 Shortest Path Algorithms 21 o For all edges u7 v 13u v is nonnegative 1784 Johnson s Algorithm 0 Reweighing Graph 0 First Try 0 Smallest weight is 7w for some positive w 0 Add w to each edge in the graph 0 Is this a valid reweighing 1785 Johnson s Algorithm 0 Reweighing Graph 0 First Try 0 Smallest weight is 7w for some positive w 0 Add w to each edge in the graph 0 Is this a valid reweighing B 5 C V4 A 4gt D 1786 Johnson s Algorithm 0 Reweighing Graph 0 Second Try 0 De ne some function on vertices hv 0 1241171 wuv hu 7 hv 0 Does this preserve shortest paths 1787 Johnson s Algorithm 0 Letp v07v17v27iii7vk beapathinG 0 Cost ofp under 12 k 7M 2724112217111 k wvi717vi M1571 MUD k wvi717vi MUD MUM we mm 7 hm CS6732008F 17 Shortest Path Algorithms 22 0 Thus any shortest path under w will be a shortest path under 12 and viceversa 1788 Johnson s Algorithm 0 So if we can come up with a function hV such that wu7 v hu 7 hv is positive for all edges u7 v in the graph we re set 0 Use the function h to reweigh the graph 0 Run Dijkstra s algorithm V times starting from each vertex on the new graph calculating shortest paths 0 Shortest path in new graph shortest path in old graph 1789 Johnson s Algorithm 0 Add a new vertex 3 to the graph 0 Add an edge from s to every other vertex with cost 0 0 Find the shortest path from s to every other vertex in the graph 0 hv 557 1 the cost of the shortest path from s to v 0 Using this hV function all new weights are guaranteed to be nonnegative 1790 Johnson s Algorithm 0 hv 557 1 the cost of the shortest path from s to v 13u7v wuv hu 7 hv 700 5710 557 v 0 Since 6 is a shortest path 587 0 687u wuv wuv 68711 7 587 0 1791 Johnson s Algorithm CS6732008F 17 Shortest Path Algorithms 1793 Johnson s Algorithm CS6732008F 17 Shortest Path Algorithms 1795 Johnson s Algorithm Graduate Algorithms CS6732008F14 Disjoint Sets David Galles Department of Computer Science University of San Francisco 140 Disjoint Sets 0 Maintain a collection of sets 0 Operations 0 Determine which set an element is in 0 Union merge two sets 0 Initially each element is in its own set 0 of sets of elements 141 Disjoint Sets 0 Elements will be integers for now 0 Operations 0 CreateSetsn Create n sets for integers On1 Unionxy merge the set containing x and the set containing y Findx return a representation of x s set Findx Findy iff xy are in the same set 142 Disjoint Sets 0 Implementing Disjoint sets 0 How should disjoint sets be implemented 143 Implementing Disjoint Sets 0 Implementing Disjoint sets First Try 0 Array of set identifiers Seti set containing element i 0 Initially Seti i 144 Implementing Disjoint Sets 0 Creating sets 145 Implementing Disjoint Sets 0 Creating sets pseudoJava void CreateSetsn for i0 iltn i Seti i 146 Implementing Disjoint Sets 39 Find 147 Implementing Disjoint Sets 0 Find pseudoJava int FindX return SetX 143 Implementing Disjoint Sets 0 Union 149 Implementing Disjoint Sets 0 Union pseudoJava void UnionXy setl SetX set2 Sety for i0 i lt n i if Seti set2 Seti setl 1410 Disjoint Sets O 0 CreateSets 0 Find 0 Union 1411 Disjoint Sets 0 0 CreateSets n 0 Find 91 0 Union n 1412 Disjoint Sets 0 0 CreateSets n 0 Find 91 0 Union n We can do better At least for Union 1413 Implementing Disjoint Sets ll 0 Store elements in trees 0 All elements in the same set will be in the same tree 0 Findx returns the element at the root of the tree containing x o How can we easily find the root of a tree containing x 1414 Implementing Disjoint Sets ll 0 Store elements in trees 0 All elements in the same set will be in the same tree 0 Findx returns the element at the root of the tree containing x o How can we easily find the root of a tree containing x 0 Implement trees using parent pointers instead of Children pointers 1415 Trees Using Parent Pointers 0 Examples 23 1416 Implementing Disjoint Sets 0 Each element is represented by a node in a tree 0 Maintain an array of pointers to nodes 1417 Implementing Disjoint Sets 0 Each element is represented by a node in a tree 0 Maintain an array of pointers to nodes 5 o A A 4 gt w gtw m 1413 Implementing Disjoint Sets 39 Find 1419 Implementing Disjoint Sets 0 Find Follow parent pointers until root is reached Root is node with null parent pointer alternately root points to itself 0 Return element at root 1420 Implementing Disjoint Sets 0 Find pseudoJava int FindX Node tmp SetsX while tmpparent null tmp tmpparent return tmpe1ement 1421 Implementing Disjoint Sets 0 Unionxy 1422 Implementing Disjoint Sets 0 Unionxy Calculate Root of x s tree rootx Root of y s tree rooty Set parentrootx rooty 1423 Implementing Disjoint Sets 0 Unionxy pseudoJava void Unionxy rootX FindX rooty Findy Setsrootxparent Setsrooty 1424 Removing pointers 0 We don t need any pointers 0 Instead use index into set array l l l l l O l 2 3 4 1425 Removing pointers l l l l l l l O l 2 3 4 5 6 0 Union23 Union68 Union02 Union26 1426 Removing pointers 0 Union23 Union68 Union02 Union28 3 l l l O l 1427 Implementing Disjoint Sets 0 Find pseudoJava int FindX while ParentX O X ParentX return X 1423 Implementing Disjoint Sets 0 Unionxy pseudoJava void Unionxy rootX FindX rooty Findy Linkrootx rooty LinkXy ParentrootX rooty 1429 Efficiency of Disjoint Sets 0 So far we haven t done much to improve the runtime efficiency of Disjoint sets 0 Two improvements will make a huge difference 0 Union by rank 0 Path compression 1430 Union by Rank 0 Merging sets We want to avoid long chains of elements 0 When merging two sets which should become the parent and why 1431 Union by Rank 0 Merging sets We want to avoid long chains of elements 0 When merging two sets which should become the parent and why The tree with the largest height should be the parent Keep track of an estimate of the height of each tree until we add path compression the estimate will be exact 1432 Union by Rank 0 For each node keep a rank which is an estimate of the depth of the tree rooted at that node 0 Initially rank for each node is O 0 How should ranks be used updated 1433 Union by Rank rootX rooty Findy Linkrootxrooty unionXy F LinkXy ParentX y 1434 Union by Rank unionxy rootX FindX rooty Findy Linkrootxrooty LinkXy if rankX gt rank y Parenty X else ParentX y if rankX ranky ranky 1435 Union by Rank 0 For each node we need either the rank or the parent not both 0 We can use the same array to store both pieces of information 0 If a node 1 is not a root Parentx parent ofx 0 If a node 1 is a root Parentx O height of tree 0 Assuming we don t allow 0 to be a set if Parentx is positive then x is not a root If Parentx is O or negative then x is a root 0 note text does not do this Roots point to themselves rank is separate 1436 Path Compression 0 After each call to FindX change X s parent pointer to point directly at root 0 Also change all parent pointers on path from X to root 1437 Implementing Disjoint Sets 0 Find pseudoJava int FindX if ParentX lt 0 return X else ParentX FindParentX return ParentX 1438 Disjoint Set G 0 Time to do a Find Union proportional to the depth of the trees 0 Union by Rank tends to keep tree sizes down 0 Path compression makes Find and Union causes trees to flatten 0 Union Find take roughly time 01 on average

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

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

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