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)
まだコメントはありません。最初のコメントを書きましょう！