Disjoint Sets
Announcements
• PS2 marking done
• Q2 office hours Wednesday August 4th
• Q4 office hours Friday August 6th
• PS3 posted
• Course review module posted
• Test 2:
• Tuesday, August 10th
• 6:30 PM – 9:00 PM (you get 120 minutes during that window)
• Everything up to and including W11, but more emphasis on W7-11
• Aid sheet required
• Course evaluations
Disjoint Set ADT
MAKE-SET(x) Given element x that does not already belong to one of the sets,
create a new set {x} that contains only x. Assign x as the representative of that
new set.
FIND-SET(x) Given element x, return the representative of the set that contains
x (or NIL if x does not belong to any set).
UNION(x, y) Given two distinct elements x and y, let Sx be the set that contains x
and Sy be the set that contains y. Form a new set consisting of Sx ∪ Sy and
remove Sx and Sy from the collection. Pick a representative for the new set. As a
pre-condition, it is required that x and y each be an element of some set.
• Disjoint Set ADT manages ____________ only.
_____________ manages elements
• Each element x, manages a ______________ to DJS data
structure
• Complexity analyzed using
__________________________________ – in keeping with
context of ___________________
• Each analysis based on
___________________ where ___________ is the number
of _________________
Disjoint Set ADT: Implementations
Chalk Talk
Implementation 1: circular linked list
Chalk Talk
Implementation 1: circular linked list
WCSC: m Operations with n MAKE-SETS?
Chalk Talk
Implementation 2: Add
Chalk Talk
Implementation 2: Add
WCSC: m Operations w/ n MAKE-SETS?
Chalk Talk
Implementation 3: Union by Weight
Chalk Talk
Union by Weight continued
WCSC: m Operations with n MAKE-SETS?
Chalk Talk
New Implementation idea!
Chalk Talk
Implementation 4: Trees
Worksheet Q2
Mark in the Google Doc row for your group or in the chat when you are
finished each subquestion of Q2. If you are staying in the mainroom,
indicate in the chat when you finish Q2c (and then carry on to Q2d)
http://tinyurl.com/csc2635
If you are watching the video, pause long enough to answer Q2.
http://tinyurl.com/csc2635
Worksheet Q2 Solution
Chalk Talk
Implementation 4: Trees
WCSC: m Operations with n MAKE-SETS?
Chalk Talk
Chalk Talk Implementation 5:
Tree union by weight
•
•
Worksheet Q3
Mark in the Google Doc row for your group or in the chat when you are
finished Q3a
http://tinyurl.com/csc2635
If you are watching the video, pause long enough to answer Q3.
http://tinyurl.com/csc2635
Chalk Talk
Implementation 5 continued
WCSC: m Operations with n MAKE-SETS?
Chalk Talk
Implementation Improvement idea!
Chalk Talk
Implementation 6: Path Compression
WCSC: m Operations with n MAKE-SETS
Chalk Talk
Implementation 7: Union by Rank
Motivation? Now that we have path compression, weight isn’t
nearly as important as _____________. Instead of looking at
the exact ____________, maintain an upperbound on the
________
Called _________
•
•
Chalk Talk
Implementation 7 continued
MAKE_SET: set rank to ___
FIND-SET: ranks ___________ . Use path compression
UNION(x,y):
Node with ________ rank is new root. Its rank is ________
If x, y have equal rank, choose ______ as new root and its
rank is ___________
Chalk Talk
Implementation 7 continued
EF, BD, DE, AC, AB, BC, BE, DF, FG, …
Chalk Talk
Implementation 7: Union by Rank
WCSC: m Operations with n MAKE-SETS
Final Remarks
Worksheet Q4
Mark in the Google Doc row for your group or in the chat when you are
finished Q4 and then come back to the main room.
http://tinyurl.com/csc2635
If you are watching the video, pause long enough to answer Q4.
http://tinyurl.com/csc2635
Worksheet Q5
Mark in the Google Doc row for your group or in the chat when you are
finished Q5 and then come back to the main room.
http://tinyurl.com/csc2635
If you are watching the video, pause long enough to answer Q5a.
http://tinyurl.com/csc2635