第 2 页
Administrivia ● Fill out the weekly surveys! ○ Pacing points and feedback you have for us :); check Piazza! ● Midterm 1 solutions and grades are out! ● CSM sections are available, http://scheduler.csmentors.org/! ● Post-midterm advising appointments ○ Sign-up on Piazza or let me know if you want to talk in the discussion survey today. ● Optional online textbook! ○ You can find readings that correspond to the lecture videos under the ‘Readings’ column of the website ● Discussion survey (please fill this out!): tinyurl.com/cz-disc6-sp19
第 3 页
Also sometimes called “Union Find” Disjoint Sets ● keeps track of whether or not elements are connected ○ empires that are constantly conquering one another ○ each empire is identified by a ruling element. ● Three basic functions: Also sometimes called union(a, b) ○ connect(a, b) ■ brings b into a’s empire (a conquers b) ○ isConnected(a, b) ■ returns whether or not a and b are in the same empire. ○ find(a) ■ Returns the “ruler” of empire a.
第 4 页
Implementations of Disjoint Sets ● Disjoint sets can be implemented in multiple ways, each with its own benefits and drawbacks. ○ Quick Find → quick to find if two are connected ○ Quick Union → quick to connect ○ Weighted Quick Union → quick union, but with some optimization
第 5 页
Quick Find ● Use an array to store which set each element is in. ● Called quick find because it is very fast to find if two elements are in the same set (isConnected(a,b)), since you just need to check if id[a] = id[b]. { 0, 1, 2, 4 }, {3, 5}, {6} 0 1 2 3 6 0 1 2 3 4 5 6 4 5 int[] id 0 0 0 3 0 3 6 Analogy: Each set is an “empire” and is identified by its ruler. 0, 3, 6 are the individual rulers and all the other elements belong to their empires.
第 6 页
Quick Union Use an array to store the parent of each node ● -1 indicates that an item is a root. int[] - 0 1 - 0 3 - parent 1 1 1 0 1 2 3 4 5 6 0 1 3 6 4 2 5
第 7 页
Weighted Quick Union ● Quick Union, but always add smaller tree to larger tree ○ connect(3,8) ● This way, the tree won’t become extremely tall ● Each index holds the index of its parent element except the root which holds the negative size of the set (the optional Algorithms textbook implements Disjoint Sets in a different way). -6 0 0 0 0 0 -4 6 6 8 - 0 0 0 0 0 0 6 6 8 10 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 9 9 0 0 6 1 2 3 4 5 6 1 2 3 4 5 7 8 7 8 9 9
第 8 页
Weighted Quick Union with Path Compression When you call find (recall that union calls find as well), as you traverse to the root, reassign every node’s parent to the root. (Each node on path to the root should be reassigned) 6 find(10) 6 7 8 7 8 9 10 9 10
第 9 页
Disjoint Set Runtimes Implementation Constructor connect isConnected QuickFindDS Θ(N) Θ(N) Θ(1) QuickUnionDS Θ(N) O(N) O(N) WeightedQuickUnionDS Θ(N) O(log N) O(log N) ^ with Path compression Θ(N) Slightly more Slightly more than constant* than constant* *: See lecture for the full story.
第 10 页
Problem 1.1 What are two improvements that we made to our naive implementation of the UnionFind ADT during lecture 14 (Monday’s lecture)?
第 11 页
Problem 1.1 Solutions What are two improvements that we made to our naive implementation of the UnionFind ADT during lecture 14 (Monday’s lecture)? The naive implementation was maintaining a List<Set<Integer>>. Improvements made were: ● Keeping track of sets rather than connections (QuickFind) ● Tracking set membership by recording parent not set # (QuickUnion) ● Union by Size (WeightedQuickUnion) ● Path Compression (WeightedQuickUnionWithPathCompression)
第 13 页
0 1 2 3 4 5 6 7 8 DisjointSets have a fixed number of items - in this case items 0 through 8. To start, each item is in its own subset.
评论 (0)
暂无评论。快来抢沙发吧！