Problem Set 3

due by 11:59 p.m. on Tuesday, September 17th, 2026

General Guidelines

• In your work on this and all subsequent problem sets, you may not use any of Java’s built-in collection classes (e.g., ArrayList) unless a problem explicitly states that you may do so. We will be writing and using our own collection classes, and using the built-in classes will keep you from fully learning the key concepts of the course.

• More generally, you may not use any built-in class that we have not covered in lecture. Classes that you may use (unless specifically directed otherwise) include String, Character, Scanner, and Math.

• You are welcome to use the Arrays.toString() method when testing the methods that your write. However, you may not use this method or any other methods from the Arrays class in the methods themselves unless a problem explicitly states that you may do so.

• You may freely use code from the class website, assigned readings, and lecture notes (unless specifically directed otherwise), as long as you cite the source in your comments. However, you may never use code from anywhere else (e.g., elsewhere on the web, or code obtained from another person). This will be considered plagiarism and penalized accordingly. See our collaboration policies for more details.

• You should continue to follow the guidelines that we gave you in the prior problem sets

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email instructor.

Make sure to follow the instructions outlined at the end of Part I and Part II when submitting your assignment.

Part I

34 points total

Creating the necessary file

Problems in Part I will be completed in a single PDF file. To create it, you should do the following:

1. Open the template that we have created for these problems in Google Docs: ps3_partI

2. Select File->Make a copy..., and save the copy to your Google Drive using the name ps3_partI.

3. Add your work to this file.

4. Once you have completed all of these problems, choose File->Download->PDF document, and save the PDF file on your machine. The resulting PDF file (ps3_partI.pdf) is the one that you will submit. See the submission guidelines at the end of Part I.

Problem 1: A Rectangle class revisited

12 points total; individual-only

Given the Rectangle class defined here.

1. Consider a potential non-static method named scale that would scale a Rectangle object by the specified integer parameter. For example, if a Rectangle‘s dimensions are 10 x 30, then calling the scale method with a parameter of 2 would change its dimensions to 20 x 60. Because the method only needs to change the internals of the called object, it doesn’t need to – and should not! – return a value.

   1. (1 point) What type of instance method would scale be, an accessor or mutator?

   2. (2 points) Give an appropriate method header for this instance method. You do not need to define the body of the method. Assume that you can both increase and decrease the size of the Rectangle using the scale method.

2. Now consider a potential non-static method named smallerThan that takes another Rectangle object and determines if the called Rectangle object (i.e., the one on which the method is invoked) has a smaller area than the other Rectangle object – returning true if the called object has a smaller area and false otherwise.

   1. (1 point) What type of instance method would smallerThan be, an accessor or mutator?
   2. (2 points) Give an appropriate method header for this method, making sure to take into account the fact that the method is non-static. You do not need to define the body of the method.

3. Consider the following client code — i.e., code from another class that uses a Rectangle object:

   Rectangle r1 = new Rectangle(60, 80);
   System.out.println("r1's width is: " + r1.width);
   r1.height = r1.height + 20;
   System.out.println(r1);     // print the new dimensions
   

   Because our Rectangle class employs appropriate encapsulation, this code fragment will not compile.

   1. (2 point) Explain what problems are present in the code fragment that prevent it from compiling.
   2. (4 points) Rewrite the fragment to eliminate those problems while maintaining the intended functionality of the original version. Don’t make any unnecessary changes.

Problem 2: A class that needs your help

8 points total; individual-only

Consider the following class, which is intended to serve as a blueprint for objects that encapsulate two pieces of data: an odd integer and a non-negative real number:

public class Pair {
    int x;
    double y;

    public static double difference() {
        return this.x - this.y;
    }
}

1. (2 points) The method difference is supposed to be an instance method that returns the difference of the two fields inside a Pair object. However, when we attempt to compile this class, we get error messages that indicate that difference cannot access the fields. In section 2-1 of your copy of ps3_partI (see above), explain why the method cannot access the fields, and what change or changes are needed to fix things.

2. (6 points) This class does not employ appropriate encapsulation. In section 2-1 of ps3_partI, revise the class to prevent direct access to the internals of a Pair object while allowing indirect access through appropriate methods. Your revised version should include:

   • the changes that you proposed above in your answer for 2-1
   • whatever steps are needed to prevent direct access to the fields
   • accessor methods that can be used to obtain the value of each field
   • mutator methods that can be used to change the value of each field. These methods should ensure that x is always odd, and that y is greater than or equal to 0.0. Attempts to assign an invalid value should produce an IllegalArgumentException.
   • a constructor that takes values for x and y and initializes the fields using those values. Attempts to assign an invalid value should produce an IllegalArgumentException. Take advantage of the error-checking code that is already present in the mutator methods that you defined for changing the values of the fields.

   No other methods are required.

Problem 3: Static vs. non-static

14 points total; individual-only

When designing a blueprint class, we have seen that we can include both static and non-static variables. Static variables (also known as class variables) belong to the class as a whole. Non-static variables (also known as instance variables or fields) belong to individual objects of the class; each object gets its own copy of those variables.

We have also seen that a blueprint class can include both static and non-static methods. A non-static method is required if the method must have access to the fields of a particular called object. However, if a method doesn’t need a called object – i.e., if all of the information that it needs is supplied by its parameters or by the static variables of the class – then we typically make it static. Non-static methods must be called on an object of the class. Static methods may be called on an object of the class, but it is better style to call them using the name of the class instead.

Imagine that we are defining a class called Grade that will serve as a blueprint for objects that encapsulate the raw score and the possible late penalty associated with a given grade. For example, to create a Grade object that represents a grade with a raw score of 85.5 and a late penalty of 20%, we would write:

Grade g = new Grade(85.5, 20);

An initial implementation of this class can be found here.

1. (4 points) Imagine that we want to modify the existing Grade class so that each Grade object has an associated category — a String that is either "assignment", "quiz", or "exam". In addition, we want to keep track of how many Grade objects have been created for each of the three categories. What variables (static and/or non-static) would we need to add to the Grade class as part of our implementation of these changes?

   In section 3-1 of ps3_partI, we have included a table that you should complete to describe the necessary variables. For each of your proposed variables, you should specify:

   • its type and name (make it descriptive!)
   • whether it will be static or non-static
   • a brief description of its purpose, and why it needs to be static or non-static.

   As an example, we have filled in the first row of the table to describe the existing rawScore field. You should add the descriptions of your proposed new variables. You may not need all of the rows in the table.

2. (4 points) Now let’s say that we want to add a method called setCategory that takes in a category string and uses it to change the category of the called Grade object.

   1. What type of method should setCategory be — static or non-static? Explain briefly.
   2. Assume we have a Grade object whose current category is "quiz". The professor who assigned the grade has decided to make the associated test worth more, so we need to call setCategory to change the grade’s category to "exam". During that method call, what changes will the method need to make to the values of the variables that you proposed above? Be as specific as possible.

The remaining sections of this problem consider two other new methods for the Grade class – methods that do not involve the grade’s category.

3. (3 points) Now let’s say that we want to add a method called computePercent. It takes two parameters of type double – one called pointsEarned and another called possiblePoints – and it returns pointsEarned as a percentage of possiblePoints. For example, if pointsEarned is 30.0 and possiblePoints is 50.0, the method should return 60.0, because 30 is 60 percent of 50.

   1. What type of method should computePercent be — static or non-static? Explain briefly.
   2. Give an example of how you would call this method from outside the Grade class. If you need a Grade object to call the method, assume that the variable g represents that object, and that the object has already been created. However, you should only use g if doing so is absolutely necessary.

4. (3 points) Finally, let’s say that we want to add a new method called addExtraCredit. It takes a parameter of type double called amount and increases the raw score of a Grade object by the specified amount.

   1. What type of method should addExtraCredit be — static or non-static? Explain briefly.
   2. Give an example of how you would call this method from outside the Grade class. If you need a Grade object to call the method, assume that the variable g represents that object, and that the object has already been created. However, you should only use g if doing so is absolutely necessary.

Submitting your work for Part I

Note: There are separate instructions at the end of Part II that you should use when submitting your work for that part of the assignment.

Submit your ps3_partI.pdf file using these steps:

1. If you still need to create a PDF file, open your ps3_partI file on Google Drive, choose File->Download->PDF document, and save the PDF file in your ps3 folder.

2. Login to Gradescope by clicking the link in the left-hand navigation bar, and click on the box for CS 112.

3. Click on the name of the assignment (PS 3: Part I) in the list of assignments on Gradescope. You should see a pop-up window labeled Submit Assignment. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

4. Choose the Submit PDF option, and then click the Select PDF button and find the PDF file that you created. Then click the Upload PDF button.

5. You should see a question outline along with thumbnails of the pages from your uploaded PDF. For each question in the outline:

   • Click the title of the question.
   • Click the page(s) on which your work for that question can be found.

   As you do so, click on the magnifying glass icon for each page and doublecheck that the pages that you see contain the work that you want us to grade.

6. Once you have assigned pages to all of the questions in the question outline, click the Submit button in the lower-right corner of the window. You should see a box saying that your submission was successful.

Part II Programming Problems

66 points total

Problem 4: Set Class: A Custom Data Type to represent a set of integers

66 points total;

This is the only problem of the assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

Overview

In mathematics and computer science, a set is a collection in which order does not matter and there are no duplicates. There are several well-defined operations which can be performed on sets, namely: union, intersection, and difference.

Additionally, when working with sets you often want to know the cardinality of the set, whether or not it is an empty set, and whether one set is a subset of another set.

Example, given two sets A and B:

A = {5,4,3,2,1}
B = {3,2,7,9}
A union B = {5,4,3,2,1,7,9}
A intesection B = {3,2}
A difference B = {5,4,1}
B difference A = {7,9}

{} is the empty set

{3,4,5} is a subset of {1,2,3,4,5} because all the elements in the first set exist in the second
{3,4,5,6} is not a subset of {1,2,3,4,5} because the element 6 of the first set is not int the second set

In this problem, you will write a class named Set which will allow you to create an object to represent a Set of integers. Each instance of the class will represent one Set and the integers that make-up the set (i.e. the elements of the set) will be stored in an array of type int. You will also implement as methods all the operations that can be performed on sets.

These are the members that need to be declared in your Set class. The array that stores the elements of the set should be initially created using the DEFAULT_SIZE static variable. However, as elements are added to the set, if the set reaches capacity and you cannot add another element, you can use the resize method (which you will implement) to grow the array so that you can add additional elements.

private static final int DEFAULT_SIZE = 10;   // class level variable to create the (inital) size of set
private int[] set;            // instance variable to reference the integer array that contains the elements
private int next;             // instance variable representing the index of the next available slot in set

Thus, a Set [ 2, 3, 7, -3 ] would be represented as follows:

and the empty set [] would be represented as:

Do not confuse the static variable DEFAULT_SIZE and the length of the array. The static variable is a class level variable used to create the initial array. As a final variable, the value will remain fixed. The length of the array (i.e. set.length) indicates the physical size of the array and may change as the array grows.

The data member next refers to how many elements are in the set and should be incremented as a new element is added to the set.

The cardinality of the set is represented by member next, and the total number of elements that the set can hold is represented by set.length.

The idea is that you can represent a Set of up to set.length integers stored consecutively in indices from position 0 to next-1.

Note that sets cannot contain duplicates elements, and this should not be allowed.

The Methods of the Set Class

public Set() -- No argument constructor; initialize this set as an
   instance of the empty set.

public Set(int[] arr) -- Initialize this set consisting of exactly
   the elements in the array referenced by `arr`. Note that the array referenced by 
   arr may contain duplicate values, but the array representing the 
   set should not. The array passed can be of arbitrary length 
   (i.e. it may or may not be smaller than SIZE). Therefore,
   you may need to *grow* the set to store all the elements.

public Set clone() -- Return an exact copy of this set

   (Hint: Consider how you can use the previous constructor to help.)

public String toString() -- Return a string representation of this set,
   e.g., [2,3,7,-3]  or {} for the empty set; 
   you may not use `Array.toString` to do this, you must build the
   resulting string.

public int cardinality() -- Return the number of elements in this set.

public  boolean isEmpty() -- Return true if this is the empty set has
   no members and false otherwise.

public boolean subset(Set S) -- Returns true if this set is a subset of S,
   that is, every member of this set is a member of S, and false
   otherwise.

public boolean equal(Set S) --  Returns true if this set and S have
   exactly the same members.

public void delete(int k) -- If the integer k is not a member, do nothing;
   else remove it from the set; you must shift all elements which occur
   after k in the array to the left by one slot.

public Set union(Set S) -- Return a new set consisting of all of the
   elements of this set and S combined (without duplicates). Example:

public Set intersection(Set S) -- Return a new set consisting of the elements
   that are common to both this set and S (without duplicates). Example:

public Set setdifference(Set S) -- Return a new set consistng of all the 
   elements of this set that are not present in S.

public boolean member(int n) -- Return true if n is in the set and false
   otherwise.

   (Hint: consider how you can use this method to help simplify your
    implementation of other methods.)

public void insert(int k) -- If the integer k is a member of the set
   already, do nothing, otherwise, add to the set; if this would cause an
   ArrayOutOfBoundsException, call resize() (provided in template code) to
   increase size of array before doing insertion.

   (Hint: This method is key to correctly implementing all many of the other
   methods without duplicating a lot of code!)

private void resize() -- Thie method should be called when there is no 
   additional capacity in the existing array and you need to 
   allow for additional elements to be added to the set.

   (Hint: Create a new array larger than the existing array, copy all the elements of the
    existing array to the new array, and update the `set` reference appropriately.)

Completing your Solution

Begin by downloading the template: Set.java. This template has most of the methods commented out. Begin by implementing the constructors and any other method which may help you correctly insert new elements into the set. You can uncomment each method one at a time as you implement it.

You can also download the file DriverForSet.java which contains a main program that you can use as a guide to incrementally test the methods of your Set class.

Submitting Your Work

• You have read the Java Style Guide (linked on Course page)and followed all guidelines regarding format, layout, spaces, blank lines, and comments;
• ensured that the signature of the methods specified in the assignment have not been changed.
• You have verified that your programs satisfy all the performance tests in the templates;

Submitting your work for Part II

You should submit only the following files:

• Set.java

Here are the steps:

1. Click on the name of the assignment in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

2. Add your files to the box labeled DRAG & DROP. You can either drag and drop the files from their folder into the box, or you can click on the box itself and browse for the files.

3. Click the Upload button.

4. You should see a box saying that your submission was successful. Click the (x) button to close that box.

5. The autograder will perform some tests on your files. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.

   Note: You will not see a complete Autograder score when you submit. That is because additional tests for at least some of the problems will be run later, after the final deadline for the submission has passed. For such problems, it is important to realize that passing all of the initial tests does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.

6. If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.

7. Near the top of the page, click on the box labeled Code. Then click on the name of each file to view its contents. Check to make sure that the files contain the code that you want us to grade.

Last updated on February 11, 2026.