Programming question for Homework 3

Design and implement Java classes for representing and manipulating generic disjoint sets. You will use a tree set representation, similar to the one described in the textbook. A set consists of a Set class instance, and zero or more Element class instances, one for each element that is a member of the set. The Element instances are arranged as a tree, the root of which is the set representative Element instance (i.e., the Element instance that corresponds to the set representative element). Each Element instance that is not a set representative keeps a reference to its parent Element instance in the tree. A representative Element instance keeps a reference to the Set instance of the set, instead. A Set instance contains set size, and a reference to the set representative Element instance. Your set implementation should support efficient FindSet and Union operations. The FindSet operation should provide the option of using the path compression heuristic. The Union operation should implement union by size.

For more details, including exact specifications of the methods that you should implement, see the starter code. All of your work must be done inside the Element and Set classes, where indicated by comments that start with: "// TODO:". You may also add appropriate instance variables or helper methods. The tester that we provide below is very basic, running it successfully does not guarantee that your code is correct or will pass our marking tester routine. You are encouraged to derive your own  test cases.

• Element.java
• Set.java
• SetTester.java

Submission Instructions:

1. Submit your code using the "submit" mechanism on fissure (by 5:30pm on Thursday, March 8). Use the following command from the directory containing your solution: submit -N PGM3 cscb63s Set.java Element.java
   The command "man submit" contains general instructions for submitting your code electronically.


2. Submit only two .java files: Element.java and Set.java of the starter code (after you have implemented the missing parts) to the directory called PGM3. All the code that you implement should be inside this file.


3. Do not submit any other file, and in particular, do not submit any class files. If you do, we will delete them before we compile your code.


4. Do not submit any printout of the code.


5. Do not rename the files, or any of the methods and variables found in our starter code.


6. Fill in your name, student number and username in the comment at the top of the Set.java file. If you have a partner, you should also fill in the corresponding information about your partner.


7. We will test your code using our own tester code. The tester that we provide is very basic, running it successfully does not guarantee that your code is correct or will pass our marking tester routine. You are encouraged to derive your own test cases.


8. Your code must compile and run on the standard Unix/Linux system of your campus (cdf/fissure/cslinux). Test it there! Programs that do not compile and run get 0 marks.

Examples: