Read the instructions carefully before writing any code!!
In this phase of the assignment, you will:
- Implement your proposed solution to the problem
- Implement a data structure designed specifically for this application (called a union find or disjoint set)
- Show that both solutions solve this problem
- Compare the running times of the two data structures on a pathological case
Part 1
Create an interface for the ADT described in phase 1. Were not going to include listMembers, so dont include it in your interface!
Part 2
Write a class that implements that interface using the strategy you came up with in phase 1. It should be generic because well be testing with Strings (the stated problem in phase 1), and Integers (for testing timings in the pathological case)
Part 3
Write a union find data structure that implements the same interface as your solution. The Union find works as follows:
The union find data structure is a forest data structure (a bunch of trees). A node stores a value, its rank, and its parent. The rank is essentially the height of the subtree rooted at that node.
Each element in your data structure (in our example problem, an element is a students name), will have an associated node. Youll need to be able to efficiently retrieve an elements node; think about how you might achieve this.
The ADT operations can be implemented via the following pseudocode:
MakeSet(T data): create a node containing data. It will be its own parent and will have rank 0.
CombineGroup(T a, T b): Compute repA = find(a), repB = find(b). If repA and repB are the same, then a and b are already in the same set and you dont need to do anything. Otherwise, assume repA lower rank than repB. set repAs parent to be repB (if repB has lower rank, do the opposite). If the ranks are equal, increase the rank of whichever node is the new parent. For example, if repA and repB both have rank 2, you could set repAs parent to be repB, and repBs new rank would be 3 (repAs rank doesnt change).
Find(T data): You probably want to implement this using a helper method that takes and returns a node:
1 | Node<T> findNode(Node<T> n): |
if n.parent == n, then n is the representative of its group, so return it
otherwise: set n.parent to findNode(n.parent) and then return ns new parent.
This method flattens all the nodes in the tree on the path from n to the root (its representative), and make any subsequent find operations super fast. After calling find, n and all of its ancestors will be connected directly to the root!
GetGroup(T data): this method can be implemented using a traversal
Part 3
Write a function called groupStudents that takes the interface you defined as a parameter. This will allow you to call the function with either YOUR implementation OR the UnionFind data structure. This function should load the input file, use the data structure to compute and then print the list of students in each group. Note: there is no operation in the ADT that gives you the list of groups, so youll have to figure out how you can use the supported operations to do so.
Here is a sample input file: sampleInput.txt
Part 4
Compare the two implementations for the pathological case described below. In this example, all of the elements will be combined into a single group as slowly as possible.
The elements will be the integers from 0 to n.
Combine the groups as follows until there is a single group
First combine 0 and 1, 2 and 3, 4 and 5, etc, so you have n/2 groups with 2 elements each
Then combine 0 and 2, 4 and 6, 8 and 10, etc. Youll have n/4 groups with 4 elements each repeat this process until everything is in a single group.
This test case will require lots and lots of unions with groups of equal size, which will be the worst case for either implementation for the ADT.
Time this testcase for various values of n, for both implementations and report your results.