Contents:

Introduction

In this assignment, you will practice writing code in an ADT, choosing how to represent an ADT, and verifying your code by reasoning as well as writing tests. The two ADTs you will be working with are FiniteSet and SimpleSet. Here, FiniteSet represents a finite set of real numbers, while SimpleSet represents either a finite set of real numbers or its complement (everything but finitely many points). By the end of assignment, you will have implemented methods that help display these sets or perform set operations, as well as unit tests for some of those methods.

Before starting this assignment, be sure that you are up-to-date on our lecture material on ADTs and testing. (You can review the same material by reading the resource pages on abstraction functions / representation invariants and testing .) These instructions assume that you are familiar with this material.

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 the previous ones in HW1-3, so make sure to have plenty of time for this part.

In 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 indicate in Gradescope which pages of your PDF solved which parts of the worksheet problem. The rest of the homework will have a different submission method (as described in HW2 and HW3); your PDF solution to part 1 should be the only file you submit in 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

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

Then, go to FiniteSetTest.java, and see the tests written for the constructing FiniteSet objects or checking the equals method. Here, note what the subdomains are being tested - empty sets, sets with one item, multiple items, out-of-order, etc. are all cases seen in the code. Here, an approach called “0, 1, 2” is being used, where we look at an empty object (0), an object with only one element (1) and an object with multiple elements (2). This is an approach you can use in some of your tests, though it shouldn't be the only approach used here. Different heuristics, as mentioned in the lecture, can be helpful for 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 by implementing the testUnion, testIntersection and testDifference in FiniteSetTest.java. Your test suite should cover the simple cases mentioned above, as well as some other, more complex cases that might cause errors for these specific methods. As you are writing unit tests, each assertion you have should test a specific case, such that failing a test would give you as much as possible about why the code is incorrect.

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

Part 3: Choosing a Representation for SimpleSet

After writing tests for FiniteSet, we continue with the SimpleSet ADT. Read the specification in SimpleSet.java and understand what SimpleSet represents, as well as functionality provided by each method. Here, note that a SimpleSet can represent either a set of finitely many real numbers (like FiniteSet) or all real numbers except finitely many of them (the "complement" of a finite set).

As you can see, there are no private fields defined in the SimpleSet class. You should choose a representation for SimpleSet that supports the specification written above the class and each method. You cannot change any of the method signatures or specification for this — your representation should work for the current specification given to you.

Note that it is not possible to store an infinite number of points in a Java array! Thankfully, it is also not necessary to do so. All that our representation needs to do is allow us to implement the methods of the class (toString, union, etc.). For example, when the client asks us to create the set of all points, we just need to create an object that will return "R" when toString is called, will return the same object whenever union is called (since a union with all points is all points), et cetera.

The aim of our representation should be to make it easy to implement the methods of the class. Storing infinitely many points in an array, even if it were possible, would actually make toString hard to implement. To figure out if we should return "R", we would have to look through the whole array and somehow make sure that nothing was missing. Likewise, if our class represents R \ {p1, ..., pN}, we would need to look through the infinite array and figure out that p1, ..., pN are not there. There are other representations we could use that would make this method easier to implement. We should start by considering the representations that would make toString easiest to write.

After you decide on a represention, you can declare the private fields for this representation. Make sure to include a quick explanation of your representation, as well as a suitable representation invariant and abstraction function above the private fields. You can refer to the work done in FiniteSet.java, lecture/section slides, or the page on abstraction functions / representation invariants for more help on representation invariants and abstraction functions.

Hint: You should use (instances of) FiniteSet as part of your representation. That class can already represent a finite set of points and provides the ability to perform unions, intersections, etc. You should make use of those operations, rather than re-implementing the same operations in your class.

After your representation is ready, you should also implement the constructors and the equals method accordingly. The provided tests will still fail at this point (as they make use of the complement method implemented in Part 4). However, if you want some reassurance that you have implemented these two methods properly, you can check that testEquals in SimpleSetTest.java fails on line 49, meaning that the first two checks on lines 47-48 worked correctly.

Part 4: Implementing and Testing Short Methods

Now that you have a good representation for the SimpleSet ADT, you can start implementing the methods as described in the specification above them. Implement the size and complement methods based on the representation you selected. Keep in mind that your implementation can change significantly based on your representation — if your method implementations are really complex, this might be a sign to change the representation. If you encounter this, feel free to go back to Part 3 and make necessary changes, so that the later parts are easier to implement. 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. Since there are multiple solutions possible for this part, make sure to 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.

For size, however, we have provided no tests. Instead, you must write the unit test for the size by filling in the method testSize method in SimpleSetTest.java. You should choose your set of test inputs carefully, applying the heuristics taught in class. (The approaches mentioned in Part 2 are useful here as well. However, 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 written a test with a good set of inputs and the test passes, 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.

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 inside the testToString method in SimpleSetTest.java and make sure that it fails (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.

How to Turn In Your Homework

Your answers in Part 1 should be submitted in Gradescope, as a PDF file. This should be the only part you are submitting in Gradescope.

At the end of each assignment, you must refer to the Assignment Submission Handout and closely follow the steps listed to submit the rest of your assignment. Do not forget to double check your submission as described in that handout - you are responsible for any issues if your code does not run when we try to grade it.

Use the tag name hw4-final for this assignment.

We should be able to find the following in your repository: