Part 1: Verifying Correctness of Methods

We start the assignment with the two code reasoning problems given in this worksheet. Similar to HW3, we recommend working on this part before starting the rest of the homework since you will have to test the methods covered here and implement similar ones in later parts. This code reasoning worksheet will require more work than those for HW1-3, so make sure you have plenty of time for this part.

On the worksheet, you will verify the correctness of the union and intersection operations with finite sets of real numbers. Before you start the problems, make sure you fully understand the background given in the first page. Then, for each of the two operations, you will need to fill the missing assertions to verify the correctness of the given code. You will also need to give explanations about certain parts of the code as described in the later pages.

Feel free to rewrite the problems on a separate sheet. You do not have to turn in these exact pages with the blanks filled in (though you can do that as well). It is okay to submit a scanned copy of a hand-written document as long as it is legible, so you can also print the worksheet, write your answers on that, and scan it when done.

After finishing, submit your solution as a PDF in Gradescope. Be sure to match the pages of your PDF to the problems. The rest of the homework will be submitted through tagging a commit on gitlab, as described later in the assignment; your PDF solution to part 1 is the only file you should manually submit on Gradescope.

Part 2: Writing Unit Tests for FiniteSet

When we release each homework assignment, we push the new starter files to your repository in GitLab, so you should obtain these new files by pulling from git.

The rest of this assignment is going to involve working with

• FiniteSet.java and SimpleSet.java in the directory hw-sets/src/main/java/sets,

• The test files FiniteSetTest.java and SimpleSetTest.java in the directory hw-sets/src/test/java/sets.

To start, read FiniteSet.java, understand how a FiniteSet is represented, and what each method does. Note that the union and intersection methods are the ones given in Part 1, and there is a provided method for the set difference operation.

Then, go to FiniteSetTest.java, and see the tests written for constructing FiniteSet objects or checking the equals method.

One approach used to write these tests is the “0, 1, 2” heuristic. We look at an empty object (0), an object with only one element (1) and an object with multiple elements (2).

The "0, 1, 2" heuristic is a good place to start for writing tests, but it shouldn't be the only appraoch you use. Consider other heuristics, as mentioned in lecture, when deciding which tests to write. One such heuristic is looking at the internal representation of an ADT, and giving inputs that might break the representation invariant if not implemented. The out-of-order case in the testCreation method here is an example to this approach.

With these in mind, write unit tests for the union, intersection, and difference methods in FiniteSetTest.java.

Your test suite should cover the simple cases mentioned above, as well as other, more complex cases specific to potential errors for these methods. As you are writing unit tests, each test method should test a specific case, such that failing a test would tell you as much as possible about why the code is incorrect.

We give you some starter methods: testUnion, testIntersection and testDifference in FiniteSetTest.java to give you a base for writing tests, but feel free to replace or add new methods beyond these in order to follow our unit testing standards.

You can refer to the lecture on October 17 covering testing, as well as the Guide to Testing for more hints on the test cases you can include.

Part 3: Implement the Representation of SimpleSet

Read the specification in SimpleSet.java to understand what SimpleSet represents, as well as functionality provided by each method.

As you can see, the ADT is fully documented but missing its representation: there are no private fields defined in the SimpleSet class and no Abstraction Function or Representation Invariant.

A SimpleSet either represents a finite set, or a set only excluding a finite set, however it is not possible to store an infinate number of points in a set. We will utilize the other ADT we have worked with for this assignment, FiniteSet, and create two FiniteSet objects which will allow us to represent finite and infinite sets distinctly.

If a set is finite, the first of two FiniteSets in our representation will be used to contain all of the points IN the set, and the unused (second) set will be null.

If the set is infinite, the second of the two FiniteSets will be used to contain all of the points NOT in the set, and the unused (first) set will be null.

Your task is to declare private, well-named fields to follow this representation and write a suitable Representation Invariant (defining the rules of the state of the representation) and Abstraction Function (translating the abstract representation to the actual representation) above the private fields. Refer to FiniteSet.java, lecture/section slides, or the Writing Rep Invariants and Abstraction Functions handout for more help on representation invariants and abstraction functions.

Once your representation is complete, implement the SimpleSet constructors and the equals method. The SimpleSets that we create in the test suite rely on the complement method which we do not implement until part 4, so the tests provided for the equals method will not all pass yet. To get some reassurance that you're on the right track testEqualsEmptySet, testEqualsSingleton, and testEqualsComplexSet in SimpleSetTest.java should fail on lines 82, 93, and 108 respectively.

Part 4: Implementing and Testing Short Methods

Now that you have a good representation for the SimpleSet ADT, you can implement its methods as described in the specifications above them. Specifically, implement size and complement to start. As a reference, the staff solution for these methods were very short.

While implementing these methods, you should also include explanations as to why your code is correct. These are not meant to be formal assertions, they are supposed to be easily readable by someone looking at your code. Explain your solution thoroughly, so that it's easy to understand why the code works. As a minimum, you should explain how your answer is calculated based on the type of SimpleSet you are working with (finite, or complement of finite), even if you don't use any if/else statements. To get full credit, your code should be not just correct, but also easy to understand.

Once you have implemented complement, the testEquals and testComplement tests provided in SimpleSetTest.java should now pass.

However, for size, we have provided no tests, so you will need to write them yourself in SimpleSetTest.java. We have given you an empty method testSize to fill out, but add additional methods to best test a single subdomain at a time. You should choose your set of test inputs carefully, applying the heuristics taught in class. (The approaches mentioned in Part 2 are useful here also, but keep in mind that SimpleSet will likely require more cases due to the fact that it can represent more types of sets than FiniteSet.) Once you have tested a good set of inputs and the tests pass, you can move on to the next problem.

Part 5: Implementing More Complex Methods

We continue with the more complex methods union, intersection, and difference.

Start by implementing the union method. You should take advantage of the methods of FiniteSet that are already available. These will allow you to form the union of two finite sets. However, you must also handle the cases where one or both of the SimpleSets involved are not finite but rather the complement of finite sets.

Similar to the previous part, you should include comments explaining why the code is correct. As a minimum, you should explain how your method behaves with every combination of SimpleSet types. Each of the two sets can be either finite or finite complement, so there are four possible combinations. To get full credit, your code should be not just correct but also easy to understand.

When you are done with your implementation, you should check your solution by running the tests for union provided in SimpleSetTest.java.

Next, implement the methods intersection and difference. These can be implemented in a similar manner to union. However, there are simpler / shorter ways to implement them using ideas from CSE 311. Either solution is acceptable.

As with union, you should include comments explaining why the code is correct for each combination of SimpleSet types. Even if your implementation handles some combinations with the same code, your comments should explain each of these cases. To get full credit, your code should be not just correct but also easy to understand.

When you are done with your implementation, you should check your solution by running the provided tests for these methods in SimpleSetTest.java. At this point, all provided tests and all tests you have written so far should be passing.

Part 6: Implementing and Testing toString

For the last part of the assignment, we work with toString. Read the specification, and understand what the output should be in each case.

Then, write unit tests for it in SimpleSetTest.java. Again, we give you a starter method, testToString, but add methods as you see fit so each method tests a single subdomain. Make sure that these tests fail (as it should since toString is not yet implemented). You can refer to Part 2 and 5 for hints on which cases you can test. Keep in mind that you should not expect your method to round floating point numbers (to a number of decimal places other than the default).

After your test suite is finished, implement toString based on the specification. For any loop in your implementation, make sure to include a loop invariant. Additionally, you should include a comment explaining why the code works, similar to what was asked in previous parts. To do this, you can use a StringBuilder, which is helpful for building a string. You should not round floating point numbers, you can just add them to your string with default formatting.

After both your tests and implementation are finished, you can check your answer by running your tests. While passing tests is not a guarantee that your code works correctly, writing tests before the implementation makes it less likely for you to repeat the same mistakes in both.