Skolan för
datavetenskap
och kommunikation
KTH / CSC / Kurser / DD2440 / avalg09 / Homework / 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.

1. Let makeSet, union, and findSet be the three operations of the union-find data structure implemented with a linked-list representation using the weighted-union 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)
```
2. 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 weighted-union heuristic. (5p)
3. Do exercise 1 using a disjoint-set 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)
4. 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)
5. 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)