Reading: Chapters 21 and 34 (15 and 16 to read ahead)
1.
Show the final data structure and give the answers to the
FIND-SET operations for the following sequence of operations
using the implementations in Section 21.2. (When two lists of
the same length are combined by a UNION operation assume the head with
the smaller key becomes the new head.)
for i=1 to 20
do MAKE-SET(i)
for i=1 to 11 by 2
do UNION(i+1,i)
for i=1 to 6
do UNION(i+12,2i)
UNION(19,13)
UNION(20,18)
for i=1 to 9 by 4
do UNION(i+3,i)
FIND-SET(16)
FIND-SET(20)
UNION(10,14)
FIND-SET(17)
FIND-SET(20)
2.
Repeat the previous problem using the implementations from
Section 21.3.
(Note that in the pseudo-code for LINK when two sets whose roots have
the same rank are combined the root of the second set becomes the new root.)
Solutions
(pdf)
Access to Solutions