Chapter 21 Answers

Question

What is G=(V, E)? G is the pair of V and E.
What is V[ G ]? {a,b,c,d,e,f,g,h,i,j}
1. Is b Î V[ G ]? Yes.
2. Is z Î V[ G ]? No.
What is E[ G ]? {(a,b),(b,a),(a,c),(c,a),(b,d),(d,b),(b,c),(c,b),(e,f),(f,e),(e,g),(g,e),(h,i), (i,h)}
1. Is (b, d) Î E[ G ]? Yes.
2. Is (b, e) Î E[ G ]? No.
What does MAKE-SET do? Create singleton sets for each vertex: {a}, {b}, {c}, ..., {j}.
Step through the execution of CONNECT-COMPONENTS for the graph G at right.
1. What is FIND-SET( b ) ¹ FIND-SET( d ) for sets {b} and {d}? True.
2. What is UNION(b, d ) for sets {b} and {d}? {b,d}
3. What is FIND-SET( b ) ¹ FIND-SET( d ) for set {b, d}? True.
After running CONNECT-COMPONENT(G), what is the result of SAME-COMPONENT(a, b)? TRUE. SAME-COMPONENT( a, e)? FALSE.

FIND-SET - Assumes the representative points to itself.

-- return the key of the representative of set x
FIND-SET (x)
if p[ x ] ¹ x then return FIND-SET ( p[ x ] )
return x
Question
Trace FIND-SET( 7 ) showing activation records. 5 is the representative, there would be activations for 7, 12, 10 and 5.
When does the worst case occur? When FIND-SET starts at the end of the linked list.
What is the precondition? A representative, p[x] = x, exists.
Give a non-recursive FIND-SET with equivalent worst case performance.
-- return the key of the representative of set x
FIND-SET (x)
while p[ x ] ¹ x do x ¬ p[ x ]
return x

UNION - Assumes the representative points to itself. Note that we do not maintain that the representative is the minimum of the union.

-- join two sets containing items x and y together
UNION (x, y)
   a FIND-SET (x)       -- a is x's representative
   b ¬ FIND-SET (y)    -- b is y's representative
   p[ a ] ¬ b                -- now b is a's parent, and FIND-SET (a) would return b
Question 
Trace the UNION( 7, 3 ) 
FIND-SET(7) returns a ¬ 5
FIND-SET(3) returns b ¬ 2
p[ 5 ] ¬ 2
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

p[ i ] 1 2 13 4 2 1 12 0 15 5 4 10 2 6 11
Draw the new set as a linked list. Does this structure support the SAME-COMPONENT procedure? Yes.
What is the estimate of the worst case for UNION of 2 sets with a total of n elements? O(n). Why? 
As in example, FIND-SET may be given an element at the end of the list.

Improvements

FIND-SET path compression

Question - For the set at right:

What is the cost in executions of the old FIND-SET(7) the first time it executes? 4

What is the cost in executions of the new FIND-SET(7) the first time it executes? 4

What is the cost in executions of the old FIND-SET(7) the second time it executes ? 4

What is the cost in executions of the new FIND-SET(7) the second time it executes? 1

What is the worst-case in executions for the new FIND-SET after the first execution? 1
 
UNION by size, weighted-union heuristic

Each UNION pushes some tree down a level. This means that the next find done on a member of this subtree will take a little longer than it would have before the UNION. Although the path is compressed during the FIND-SET, the damage is already done with the time spent doing the FIND-SET.

Example - Consider the cost of FIND-SET( 7 ) on the following uncompressed path:

The cost would be less if the larger set was the parent.

Question

For an uncompressed path, what is the worst case performance of UNION? O(n)

Modify the array for:

i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

p[ i ] 1 2 2 4 2 1 2 0 15 2 4 2 2 6 11

Union-by-size
Examples
a) Initially 6 singleton sets
    i 1 2 3 4 5 6
p[i] 1 2 3 4 5 6
c[i] 1 1 1 1 1 1
b) Union (3, 5)
    i 1 2 3 4 5 6
p[i] 1 2 5 4 5 6
c[i] 1 1 1 1 2 1
c) Union (4, 2)
    i 1 2 3 4 5 6
p[i] 1 2 5 2 5 6
c[i] 1 2 1 1 2 1

d) Union (2, 6)
    i 1 2 3 4 5 6
p[i] 1 2 5 2 5 2
c[i] 1 3 1   1 2 1
e) Union (1, 4)
    i 1 2 3 4 5 6
p[i] 2 2 5 2 5 2
c[i] 1 4   1 1 2 1
f) Union (3, 6)
    i 1 2 3 4 5 6
p[i] 2 2 5 2 2 2
c[i] 1   6 1 1 2 1

Question

In b), which element is the representative of {3, 5}? 5

In d), what is the set(s)? {2, 4, 6} and {3, 5}

In e), which element is the representative of {1, 2, 4, 6}? 2

In f), what is the set and which element is the representative? {1,2,3,4,5,6}, 2

After f), trace the execution of FIND-SET( 3 ). What is p?

i 1 2 3 4 5 6

p[ i ] 2 2 2 2 2 2

a) Initially 6 singleton sets i 1 2 3 4 5 6 p[i] 1 2 3 4 5 6 c[i] 1 1 1 1 1 1	b) Union (3, 5) i 1 2 3 4 5 6 p[i] 1 2 5 4 5 6 c[i] 1 1 1 1 2 1	c) Union (4, 2) i 1 2 3 4 5 6 p[i] 1 2 5 2 5 6 c[i] 1 2 1 1 2 1
d) Union (2, 6) i 1 2 3 4 5 6 p[i] 1 2 5 2 5 2 c[i] 1 3 1 1 2 1	e) Union (1, 4) i 1 2 3 4 5 6 p[i] 2 2 5 2 5 2 c[i] 1 4 1 1 2 1	f) Union (3, 6) i 1 2 3 4 5 6 p[i] 2 2 5 2 2 2 c[i] 1 6 1 1 2 1