A partition of a set S is a collection of subsets of S such that each element of S is in exactly one of the subsets. Here are some examples of partitions of the set S = {0, 1, 2, 3, 4, 5}:

{0, 2, 4} and {1, 3, 5} {0, 1, 3}, {2, 5} and {4} {0, 1, 3, 4} and {2, 5} {0}, {1}, {2}, {3}, {4} and {5} {0,1,2,3,4,5} on its own.

The following are not partitions of S = {0, 1, 2, 3, 4, 5}:

Sets {0, 1}, {2, 4} and {5} {0, 1, 3}, {2, 3, 4} and {5} {0,1,2,3} and {4,5,6}

Not a partition because... 3 not in any subset 3 in two subsets {4,5,6} not a subset.

In this assignment, you will use a tree-based data structure to represent set partitions. A set partition will be represented by a collection of trees. Each tree will represent one subset, and will have one node for each element of that subset. Here are four different representations of the partition {0, 1, 3, 4} and {2, 5} as trees.

The individual trees may have any shape and they are not necessarily binary. All that matters is that each tree has a node for each element of the subset it represents, and no more. We can determine whether two elements are in the same subset by finding the roots of their trees. In the first example, the root of 1s tree is 0, and so is the root of 0s tree, so we may conclude that 1 and 0 are in the same subset. The advantage of using trees (instead of e.g., lists) is that even large trees can be shallow, which makes finding the root fast. We will represent the trees using a Node class. Each node will contain an int value and a reference to the nodes parent (null if there is no parent). For this assignment, we only need to store a nodes parent, not its children. We could, in principle, use other data structures such as lists to represent set partitions.

The advantage of using trees is that, if we can make the trees shallow, it is much faster to find the root of a big tree than to find the head of a big list.

1.1 Setting up (6%)

Create a class called SetPartition. It should have:

• an inner class called Node, as described above;

• an array of Node objects, one for each element of the set;

• a constructor SetPartition (int numElements). The constructor should set up the array and the Nodes to represent the partition of the set {0, 1, . . . , numElements 1} where the subsets are {0}, {1}, . . . , and {numElements 1}

  1.2 Finding roots (7%)

  Add a method public int getRoot (int x) to your class, which returns the value at the root of the tree containing x. (Note that, until youve written merge(), below, the result of getRoot() wont be very interesting, as each value will be in a subset containing only itself.)

  1.3 In the same subset? (4%)

  Add a method public boolean inSameSubset (int x, int y) that determines whether x and y are in the same subset of the partition.

• 1.4 Merging subsets (10%)

  Add a method public void merge (int x, int y) to your class. It should merge the subsets containing x and y into a single subset. If x and y are in the same subset already, there is nothing to do. If they are in different subsets, it should merge their trees by makingxs root be the parent of ys root. Note that you dont need to change the array; just the nodes.

  For example, merge (4,2) should turn the first partition below ({0,1,3,4} and {2,5}) into the second one ({0,1,2,3,4,5}). merge (5,1) should turn the first partition into the third (another representation of {0, 1, 2, 3, 4, 5}).

  1.5 Depth (7%)

  Write a method public int depth (int x) which returns the depth of xs node in its tree (giving each root depth zero). Write a method public int maxDepth () which returns the greatest depth of any node.

  1.6 Testing the code (10%)

  Write a main method that does the following.

• CreatesaSetPartitionwith1000elements,callsmerge(0,1),merge(1,2),...,merge(998,999)

  and reports the maximum node depth of the tree.

• Creates a SetPartition with 1 000 elements, calls merge(998,999), merge(997,998),

  . . . , merge(0,1) and reports the maximum node depth of the tree.

• Creates 1 000 SetPartitions each with 1 000 elements, makes 750 random merges on each one and reports the average maximum node depth of these trees. (The answer should be about 6163.)