Strategies for Solving the Dynamic Equivalence Problem
You have two choices when trying to solve the Dynamic Equivalence Problem:
It has recently been proven that both cannot be done simultaneously in constant time.
Given:
Elt. Class
0 A
1 B
2 C
3 D
4 E
5 F
6 G
7 H
Unions:
0 U 1
2 U 3
4 U 5
6 U 7
1 U 2
4 U 7
2 U 6
Find() in constant time
General Approach: Store in an array the name of the equivalence class for each elt. Then find() is just a constant lookup.
1. Sketch the original representation.
2. How would a union() operation be implemented?
3. What would the running time of a single union() be?
4. What would the running time of a sequence of N-1 unions (the maximum possible) be? Why?
A modification of this approach is to also store an array of pointers to a linked list. Then each element in an equivalence class is contained in a single linked list.
5. Show both arrays through at least five unions.
6. This will keep you from having to search through the entire array every time you do a union(), but will not decrease asymptotic run-time. Why?
Another modification to this approach is to keep track of the size of each equivalence class, and when performing union(), change the name of the smaller equivalence class to the larger equivalence class.
7. Using this approach, the total time spent for N-1 merges is O(N lg N). Why?
Union() in constant time:
This is the approach on which we will focus.
Note: Remember in find(), the name of a set doesn’t really matter. We just want to know if find(a) == find(b).
General Approach: Use a tree to represent each set. Use the root of the tree to name the set. Each node of the tree will only have a link to its parent.
(Remember awhile ago when we mentioned different tree representations and there was no obvious reason we would only want to store a node’s parent?!)
8. Draw the initial state of this representation.
9. To perform union(a,b), make the root of the tree containing node b’s point to node a. Sketch this representation after at least three unions.
This can be implemented using an array where the index of the array is the element, and the value stored in the array is the parent of the element. If the element is a root, -1 is stored.
10. Draw the array after five unions.
11. What is the running time for find()?