CPSC 225 Lab 2 Spring 2022 CPSC 225 Intermediate Programming Spring 2022 Lab 2: Correctness Due: Tue Feb 8 at the start of lab Introduction The purpose of this lab is to practice thinking about correctness as a part of program development, and to employ tools to help with ensuring correctness. Before You Start You are encouraged to complete this lab with a partner, but you may work individually if you prefer. If you work with a partner, you should practice pair programming (see the collaboration policy below) and only need to hand in one copy of the lab (make sure both names are included in each file!). Collaboration Policy Labs are for practice and learning. Getting help from others is fine, but keep in mind that the goal of lab assignments is for you to master the material, so if you are working alone, you should attempt the tasks yourself first and, after receiving help, make sure that you can explain everything in the solution and how it was arrived at. If you are working with a partner, practice pair programming (where you and your partner sit at one computer and switch off between the tasks of typing and generating ideas) rather than dividing up the task and working individually on separate parts. Setup One person should: Create a new Eclipse project named lab2. (Name it exactly as specified, lowercase and all.) Import the Java files in /classes/cs225/lab2 into the project. Make sure the imported files end up in the src directory of the project. Exercises A set is a collection of elements where the key operation is membership - whether or not an element belongs to the set. Duplicates are not allowed in a set, so inserting an element that is already in the set has no effect. Two other operations on sets are common: the union of two sets is a set containing every element present in one or both sets (without duplicates), and the intersection of two sets is a set containing every element present in both sets (without duplicates). For example, for sets { 1, 2, 3, 4 } and { 2, 4, 5 }, the union is { 1, 2, 3, 4, 5 } and the intersection is { 2, 4 }. You have been provided with a (buggy) class BoundedSet, which is an implementation of a set that has a maximum size - that is, there can be a point when the set is full and no more elements can be added until one is removed. Internally BoundedSet uses an array to hold the elements in the set, and the elements are meant to be stored in increasing order within the array. (So, for set { 2, 4 }, the array will contain 2 in slot 0 and 4 in slot 1.) This sorted order must be maintained when elements are inserted and removed. Identify class invariants, preconditions, and any other applicable invariants for BoundedSet, and state them in comments (placed appropriately) in the class definition. The find helper method uses binary search to locate a particular element (if present). The key idea of binary search is to keep track of the range of locations within the array where the element would be found if it is present, and to progressively shrink that range until the element is found or the range is empty (meaning the element isn't present). It is easy to make mistakes when implementing this algorithm, so stating this idea - that the element is within the current range of locations, or it cannot possibly be in the array because it is smaller than the smallest thing in the array or larger than the largest thing in the array - as a loop invariant can help detect problems. Add checks for the preconditions, throwing an IllegalArgumentException if a precondition is violated. Add checks for the class invariants and any other invariants using assertions. For a more complex-to-check invariant like "elements in increasing order", create a private helper method as shown below. (You'll need to fill in the body, replacing the ....) Checking the invariant then just means asserting that method returns true.
/**
* Determine if the array elements are in increasing order.
*
* @return true if the array elements are in increasing order,
* false otherwise
*/
private boolean isIncreasingOrder () { ... }
Identify a thorough set of test cases for the contains, add, and equals methods of BoundedSet. Consider both black box and white box testing. Write your test cases in comments BoundedSetTester following the template provided (and used in Monday's class - see the posted TimeTester as an example). Implement three of the test cases you've identified. Follow the pattern used in Monday's class. One challenge that can arise with testing is setting up the starting state. BoundedSet's only public constructor creates an empty set, but for many test cases, you want a set that already has some things in it. To reduce repeated code in setting up starting states, another constructor was added which allows the creation of a BoundedSet with specific contents. (Note that this constructor isn't public - it's not meant for general use, only testing, and the lack of any access modifier means that only code in the same package can use it. The similar-looking private constructor is used internally in the implementation of BoundedSet, and is not available for tester use.) Another challenge that can arise with testing is determining whether the actual result matches the expected result. BoundedSet doesn't have any public methods that let you directly access the array, but it does have toString - if the expected result is the set containing 1, 4, and 5, you can check that toString returns "{1,4,5}". Make sure you turn on assertion checking (recall the demo in Monday's class or see the slides from Fri 1/28), then run your tester. Do you find any problems? (You don't need to write an answer for this.) If You Have Time (This isn't required or graded, but it is good practice if you have extra time.) Identify a thorough set of test cases for the other public methods of BoundedSet: toString, size, capacity, isFull, remove, union, intersection. Are any of these trivial and not worth identifying test cases for? Implement the other test cases you identified in the main exercises, as well as the test cases you identified for the other public methods. Fix any bugs revealed by your tester. Handin If you worked with a partner, only one handin is needed for the group. Make sure that your name is in an @author tag in the class comments at the beginning of each file. If you worked with a partner, make sure both names are included. Make sure that all of your Java files have been auto-formatted and saved. Copy your lab2 project directory (~/cs225/workspace/lab2) to your handin directory (identified by your username in /classes/cs225/handin). It's a good idea to check that everything got handed in correctly - BoundedSet.java and BoundedSetTester.java should be in /classes/cs225/handin/username/lab2/src. last updated: --Tue Feb 1 08:56:07 EST 2022-- page owned by: bridgeman@hws.edu
