Chapter 8 (Disjoint Set ADT) Flashcards
What is used to mean an equivalence relation?
~
T/F Electrical connectivity is an equivalence relation
T
What are the two basic operations of the disjoint set?
Union and find
T/F Travelling between cities is not an equivalence relation
F, it is
We start with a list of ____ sets, each with ____ element, and no relation between the elements
N, one
T/F <= is an equivalence relation
F, it fails the symmetric property
T/F In dynamic equivalence, the operations on the sets involve comparing their relative values
F, it does not involve comparing their relative values
What can we use to represent a set?
Tree
T/F In dynamic equivalence, actual data items would need to be mapped to these values for an application to use them
T
T/F Each set is stored as a separate tree
T
So, to know if a~b, we need to know if a and b….
belong to the same equivalence class
With dynamic equivalence, what can be used to check for equivalence in constant time?
2D array of Boolean values
What are the three properties of an equivalence relation?
Reflexive Symmetric Transitive
T/F With dynamic equivalence, the data may come to use implicitly
T
What does the union operation do?
Merges two equivalence classes into one
When all sets are unique, they are ____
Disjoint
What is a collection of trees called?
Forest
Is a tree the only way we can represent a set?
No
T/F In dynamic equivalence, the name returned is somewhat arbitrary
T
~ is used to mean a ____
Equivalence relation
What two operations do we define in dynamic equivalence?
Union and Find
What does the find operation do?
Returns the name of the set containing a given element
T/F The equivalence class of ‘a’ partitions ‘S’ into two sets, the set that relates to ‘a’ and the set that does not
T
T/F In dynamic equivalence, an array could be used by letting the index represent the element, and the value represent the set it belongs to (its name)
T
