Homework D

Avalg homework D, fall 2009
This homework is due 9/12.
It should be done individually and handed in at 10.15 at the beginning of class.
Solutions handed in late are not accepted and will not be graded.
The solutions must be printed, not handwritten.

Let makeSet, union, and findSet
be the three operations of the unionfind data structure implemented
with a linkedlist representation using the weightedunion heuristic.
Draw a picture of the data structure that results from running
the following code.
In case the sets containing i and j have
the same size, the union(i, j)
operation appends j's list to i's. (5p)
for (i = 1; i <= 16; i++)
makeSet(i)
for (i = 1; i <= 15; i += 2)
union(i, i+1)
for (i = 1; i <= 13; i += 4)
union(i, i+2)
union(1, 5)
union(12, 15)
union(6, 14)

Let n be the number of makeSet operations.
Show that the amortized time complexity is O(1)
for makeSet and findSet, respectively,
and O(log n) for union
if we use linked lists with the weightedunion heuristic. (5p)

Do exercise 1 using a disjointset forest with union
rank and path compression.
In case the sets containing i and j have
equal rank, the union(i, j) operation uses j's
root as the root of the combined tree. (5p)

Give a sequence of m makeSet, union,
and findSet operations, n of which are
makeSet operations, that takes
Ω(m log n) time
when we use union by rank only. (5p)

Show that any sequence of m makeSet,
link, and findSet operations takes
O(m) time if both union by rank and
path compression are used and all the link operations
occur before any of the findSet operations.
What happens if only path compression is used? (5p)
