Chapter 8 (Disjoint Set ADT)

Question 1

What is used to mean an equivalence relation?

Answer 1

~

Question 2

T/F Electrical connectivity is an equivalence relation

Answer 2

T

Question 3

What are the two basic operations of the disjoint set?

Answer 3

Union and find

Question 4

T/F Travelling between cities is not an equivalence relation

Answer 4

F, it is

Question 5

We start with a list of ____ sets, each with ____ element, and no relation between the elements

Answer 5

N, one

Question 6

T/F <= is an equivalence relation

Answer 6

F, it fails the symmetric property

Question 7

T/F In dynamic equivalence, the operations on the sets involve comparing their relative values

Answer 7

F, it does not involve comparing their relative values

Question 8

What can we use to represent a set?

Answer 8

Tree

Question 9

T/F In dynamic equivalence, actual data items would need to be mapped to these values for an application to use them

Answer 9

T

Question 10

T/F Each set is stored as a separate tree

Answer 10

T

Question 11

So, to know if a~b, we need to know if a and b….

Answer 11

belong to the same equivalence class

Question 12

With dynamic equivalence, what can be used to check for equivalence in constant time?

Answer 12

2D array of Boolean values

Question 13

What are the three properties of an equivalence relation?

Answer 13

Reflexive Symmetric Transitive

Question 14

T/F With dynamic equivalence, the data may come to use implicitly

Answer 14

T

Question 15

What does the union operation do?

Answer 15

Merges two equivalence classes into one

Question 16

When all sets are unique, they are ____

Answer 16

Disjoint

Question 17

What is a collection of trees called?

Answer 17

Forest

Question 18

Is a tree the only way we can represent a set?

Answer 18

No

Question 19

T/F In dynamic equivalence, the name returned is somewhat arbitrary

Answer 19

T

Question 20

~ is used to mean a ____

Answer 20

Equivalence relation

Question 21

What two operations do we define in dynamic equivalence?

Answer 21

Union and Find

Question 22

What does the find operation do?

Answer 22

Returns the name of the set containing a given element

Question 23

T/F The equivalence class of ‘a’ partitions ‘S’ into two sets, the set that relates to ‘a’ and the set that does not

Answer 23

T

Question 24

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)

Answer 24

T