Problem Set 4

Due date is 11:59 p.m. on Tuesday, February 25, 2025.

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

40 points total

Creating the necessary folder

Create a subfolder called ps4 within your cs112 folder, and put all of the files for this assignment in that folder.

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. Access and make a copy of the template that we have created by clicking on this link and signing into your Google account as needed.

2. When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.

3. Select File->Rename, and change the name of the file to ps4_partI.

4. Add your work for the problems from Part I to this file.

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

Problem 1: Understanding and using inheritance

10 points total; individual-only

Imagine that you wanted to capture information about a collection of different types of vehicles (cars, trucks, motorcycles, etc.). To do so, you could use inheritance to create a collection of related classes whose inheritance hierarchy looks like this:

We have provided an implementation of most of these classes in this folder, and we encourage you to review the provided files. They include:

• a class called Vehicle that defines the state (fields) and behavior (methods) that are common to all vehicles; it does not explicitly extend another class

• a class called Motorcycle that can be used to create objects that represent motorcycles; it inherits all of its fields and methods from Vehicle, with the exception of its own constructor

• a class called Automobile that can be used to create objects that represent cars; it also inherits fields and methods from Vehicle, but it adds some new fields and methods that are only needed by cars, and it overrides the inherited toString() method with its own version

• a class called Truck that can be used to create objects that represent trucks; it also inherits fields and methods from Vehicle, but it adds some new fields and methods that are only needed by trucks, and it overrides the inherited toString() method with its own version

• a class called Taxi that can be used to create objects that represent cars; it inherits its fields and methods from Automobile, but it adds some new fields and methods that are only needed by taxis, and it overrides the inherited toString() method with its own version

• a class called TractorTrailer that can be used to create objects that represent tractor trailors; it inherits its fields and methods from Truck, but it adds some new fields and methods that are only needed by tractor trailers, and it overrides the inherited getNumAxles() method with its own version.

The hierarchy diagram above includes a Limousine class and a MovingVan class, but we have not defined those classes yet.

In the Problem 1 section of your ps4_partI document (see above), answer the following questions:

1. (1 point) Which of the classes that are shown in the diagram above are a superclass of the TractorTrailer class?

2. (1 point) If we have a TractorTrailer object that has been assigned to a properly declared variable t, is it possible to make the following call?

   t.getMileage()
   

   Explain briefly why or why not.

3. Write a definition for the Limousine class that takes full advantage of inheritance.

   A Limousine object should have all of the same state and behavior as an Automobile object. In addition, it should maintain additional state that keeps track of:

   • whether the limousine has a sun roof (true or false)
   • how many bottles of champagne it can chill (a non-negative integer)

   When a Limousine object is printed, we should see its make, its model, and the number of seats available to customers, which is two fewer than the total number of seats. For example, if the Limousine is a Cadillac XTS-L with a total of 8 seats, printing it should produce the following output:

   Cadillac XTS-L (seats up to 6 customers)
   

   Note that the output mentions 6 seats, because only 6 of the 8 seats are available for customers.

   In your ps4_partI file, add a definition of this class that includes the following:

   1. (1 point) a class header that sets up the appropriate inheritance

   2. (2 points) whatever new fields are needed to capture the state of a Limousine object. Make sure that you take inheritance into account when deciding which fields to include.

   3. (2 points) a constructor that takes as parameters the make, model, year, and total number of seats, as well as a boolean value indicating whether the limo has a sun roof and an integer indicating how many bottles of champagne it can chill. The constructor should ensure that the object is not put in an invalid state (throwing an exception as needed), and it should take whatever steps are needed to initialize the object.

   4. (3 points) any necessary methods. It should be possible for a client to obtain the value of any of the fields, and to change the value of any field that can be changed in an Automobile object. However, you should assume that the portion of the state specifying whether there is a sun roof and how many champagne bottles can be chilled will never change, and thus mutator methods are not needed for those fields. You also don’t need to define an equals method for this class.

Problem 2: Inheritance and polymorphism

18 points total; 2 points each part; individual-only

Imagine that you have a set of related classes that have been defined using inheritance. Here are the key facts about these classes:

• Class Zoo doesn’t explicitly extend a class (i.e., it doesn’t have an extends clause in its class header). Its class members (i.e., its fields and methods) include:

  • an integer field called a
  • a String field called b
  • a non-static method called one() that takes an integer and returns a double
  • a non-static method called two() that takes no inputs and returns an integer
  • its own equals() method that overrides the inherited one.

• Class Woo extends Zoo. In addition to the members that it inherits, it has:

  • integer fields called x and y
  • its own method called two() that overrides the inherited one
  • its own toString() method that overrides the inherited one.

• Class Too extends Zoo. In addition to the members that it inherits, it has:

  • integer fields called t and u
  • its own method called two() that overrides the inherited one
  • its own method called three() that takes a double and returns a boolean
  • an equals() method that overrides the inherited one.

• Class Yoo extends Woo. In addition to the members that it inherits, it has:

  • a String field called c
  • its own method called one() that overrides the inherited one.

In addition, you should make the following assumptions:

• All of the classes employ appropriate encapsulation.

• Each class has a constructor that takes no parameters and initializes the newly created object’s fields with their default values.

• Each class includes an appropriate accessor method for each field that is declared in that class. For example, the Zoo class would have accessor methods called getA() and getB().

• Each class includes an appropriate mutator method for each field that is declared in that class. For example, the Zoo class would have mutator methods called setA() and setB().

Answer the following questions in light of the above information about these classes. Before you begin, you may find it helpful to draw an inheritance hierarchy for the classes, although doing so is not required.

1. (2 points) The information above states that the Zoo class has its own equals() method that overrides the inherited one. Where does the equals() method that Zoo overrides come from? Be as specific as possible, and explain your answer briefly.

2. (2 points) List all of the fields in a Yoo object – both the ones that it declares and the ones (if any) that it inherits.

3. (5 points) Consider the following code fragment:

   Yoo y1 = new Yoo();
   System.out.println(y1.one(10));
   System.out.println(y1.two());
   System.out.println(y1.three(12.5));
   System.out.println(y1.equals(y1));
   System.out.println(y1);
   

   Each of the println statements in this code fragment displays the result of a method call. (This includes the fifth println statement, in which the Java interpreter calls a method on our behalf.) However, it is possible that one or more of these methods calls would fail to compile because the necessary method is neither defined in the Yoo class nor inherited from a superclass of Yoo.

   In section 2-3 of ps4_partI, we have included a table that you should complete with appropriate information about each of these method calls. We have filled in the first row for you, and you should complete the remaining rows.

4. (3 points) Now imagine that you want to add a non-static method to the Too class. It should be called avg(), it should take no parameters, and it should return the average of all of the integer fields in the called Too object. Add a full definition of that method to section 2-4 of your ps4_partI file. Make sure to take into account the fact that the classes employ proper encapsulation. Make the average as precise as possible.

5. (6 points) For each of the following assignment statements, indicate whether it would be allowed according to the rules of polymorphism, and explain briefly why or why not.

   1.     Woo w = new Too();

   2.     Zoo z = new Woo();

   3.     Zoo z = new Yoo();

   4.     Too t = new Zoo();

Problem 3: Memory management and the ArrayBag class

12 points total; individual-only

In this problem, you will draw a series of memory diagrams that illustrate the execution of a program that operates on objects of the ArrayBag class from lecture.

Consider the following Java program:

public class ArrayBagTest {
    public static void main(String[] args) {
        ArrayBag b1 = new ArrayBag(3);
        ArrayBag b2 = new ArrayBag(3);
        ArrayBag b3 = b2;

        // part 1: what do things look like when we get here?

        // part 2: what do things look like at the start of
        // this method call?
        b1.add("hello");

        b2.add("world");
        b3.add("hello");

        // part 3: what do things look like when we get here?

        System.out.println(b1);
        System.out.println(b2);
        System.out.println(b3);
    }
}

1. In section 3-1 of ps4_partI, we have given you the beginnings of a memory diagram. On the stack (the region of memory where local variables are stored), we have included a frame for the main method. On the heap (the region of memory where objects are stored), we have included the ArrayBag object to which the variable b1 refers and its items array. As usual, we have used arrows to represent the necessary references.

   Complete the provided memory diagram so that it shows what things look like in memory just before the call b1.add("hello").

   To do so, you should:

   • Click on the diagram and then click the Edit link that appears below the diagram.

   • Make whatever changes are needed to the diagram. Below the thick horizontal line, we have given you a set of extra components that you can use as needed by dragging them above the thick line and putting them in the correct position. These components include String objects representing the strings "hello" and "world". You may not need all of the provided components.

   • You can also edit any of the values in a field or array by clicking on the corresponding cell and editing the text that is inside the cell.

   • Once you have made all of the necessary changes, click the Save & Close button.

2. In section 3-2 of ps4_partI, we have given you the beginnings of a memory diagram that you should complete to show what things look like in memory at the start of the execution of b1.add("hello")—just before the first statement of that method is executed.

   Note: To save time, it should be possible to select and copy some of the components of your diagram for 3-1 and paste them into your diagram for 3-2.

3. In section 3-3 of ps4_partI, we have given you the beginnings of a memory diagram that you should complete to show what things look like in memory after all of the calls to add have returned—just before the print statements execute in main().

   Note: We have included a method frame for add, but it may or not be needed in this diagram; you should delete it if you determine that it would no longer be present in memory.

4. What would be printed by this program? You may find it helpful to consult the toString method of the ArrayBag class.

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 ps4_partI.pdf file using these steps:

1. If you still need to create a PDF file, open your ps4_partI file on Google Drive, choose File->Download->PDF document, and save the PDF file in your ps4 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 4: 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

60 points total

Problem 4: BigInt: a class for large integers

60 points total; individual-only

Overview
In Java, the int data type can only represent integers from -2,147,483,648 to 2,147,483,647. This isn’t big enough to
store very large numbers—for example, the population of Earth (approximately 7.53 billion as of 2017)—or to compute n! for large values of n.

The Java libraries contain a built-in class called BigInteger to handle arbitrarily large integers. In this problem, you will write your own class called BigInt that has a subset of the functionality of the built-in Java class.

Representing integers using an array of digits
Each BigInt object will use an arrays of integers, where each element of the array represents a single digit of the integer.

We will design the class to handle non-negative integers with up to 20 digits, and thus the array will have a length of 20.

For example, the integer 57431 would be represented using this array:

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 7, 4, 3, 1}

Note that:

• Each element of the array is a single digit (i.e., an integer from 0-9).
• The last element of the array represents the least significant digit of the integer (i.e., the rightmost digit).
• The first non-zero element (if there is one) represents the most significant digit of the integer. (The one exception is when we are representing 0 itself. Its most significant digit is the same as its least significant digit, and it is a zero!)
• The remaining elements are leading zeros that are not significant digits.

As another example, the integer for 7.53 billion would be represented using the array

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 5, 3, 0, 0, 0, 0, 0, 0, 0}

Task 0: Download and review our starter code
Begin by downloading the following starter file: BigInt.java

Open this file in your IDE and review its contents. We have given you:

• a class constant called MAX_SIZE that represents the largest number of digits that a BigInt object can have. It will be used when constructing the array of digits.

• an instance member digits, which holds a reference to the array of integers in which the digits are stored. The array of digits represents the large integer.

• an instance member numSigDigits, which stores the number of significant digits in the integer. This is the same as the number of digits in the integer when it is written without leading zeroes. For example, for a BigInt that represents the integer 57431, numSigDigits should be 5, and for a BigInt that represents the integer 31, numSigDigits should be 2. This internal member should be correct for all objects, including the objects that are produced when computing the sum and the product.

• a default constructor (i.e., one that takes no arguments); it creates a BigInt object representing the number 0.

• a set of tests in the body of a main method. At the moment, these tests are commented out, but you should gradually uncomment them and run them as you add functionality to the class.

Task 1: Add your first of several custom constructors
1. Add a custom constructor with the following header:

public BigInt(int[] arr)

It should use the contents of the array that is passed in as the basis of the new BigInt object. For example, we should be able to create a BigInt for 57431 as follows:

int[] arr = {5, 7, 4, 3, 1};
BigInt val = new BigInt(arr);

Suggested approach:

• Validate that a valid array has been passed to the Constructor and, the array has a length between 0 and MAX_SIZE. If the parameter is null, if the length of the array is greater than MAX_SIZE, or if any of the elements of the array don’t make sense as digits, the method should throw an IllegalArgumentException.

  Note: You may want to consider writing a private helper method that helps validate that an element is a valid digit. In general, we encourage you to use a private helper method whenever doing so would help to decompose and simplify* your code and/or your logic.*

• Create and initialize the digits array from the input array arr. You cannot assume that the array passed to the method has a length of MAX_SIZE. It cannot have a length greater than MAX_SIZE but, it can be less. Make sure to validate each element before assigning to the digits array.

• The constructor should also determine and initialize the correct value for the numSigDigits field. Make sure that you don’t include non-significant leading zeroes in the value that you compute for numSigDigits.

Important: Make sure that the digits field ends up referring to a new array of length MAX_SIZE. You should not make it refer to the array that is passed in.

Task 2: Add two methods useful for testing
2. Add the following methods:

• an accessor method called getNumSigDigits() that returns the value of the numSigDigits field. For example, running this test code:

  int[] arr = {0, 0, 0, 5, 7, 4, 3, 1};
  BigInt val = new BigInt(arr);
  System.out.println(val.getNumSigDigits());
  

  should print a value of 5.

• a toString() method that overrides the default toString() method (the one inherited from the Object class). It should return a string that can be used to print a BigInt object in the way that we would ordinarily write the corresponding integer—with no leading zeroes. For example, running this test code:

  int[] arr = {0, 0, 0, 5, 7, 4, 3, 1};
  BigInt val = new BigInt(arr);
  System.out.println(val);
  

  should print:

  57431
  

Once these two methods are defined, you can—and should!—uncomment the first few tests in the main method, and run the class to confirm that you get the correct results.

Task 3: Add the remaining methods
3. You are now ready to implement the remaining methods of the class. After adding a given method, uncomment the corresponding tests in the main method to test it.

• public BigInt(int n)
  A constructor that creates a BigInt object representing the integer n. If n is negative, throw an IllegalArgumentException. (Note: You don’t need to worry about n being too big, because all non-negative int values can be represented using fewer than 20 digits!)

  For example, the following statements:

  BigInt val = new BigInt(1234567);
  System.out.println(val);
  System.out.println(val.getNumSigDigits());
  

  should produce this output:

  1234567
  7
  

  You will need to figure out how to determine the individual digits of the int that is passed in, and we recommend that you use concrete cases to help you. For example, let’s say that you wanted to determine the individual digits of 123:

  • What computation would allow you to determine just the units digit of 123?

  • Once you have determined the units digit, how could you compute a new integer that includes everything but the units digit? (In the case of 123, how could you go from 123 to 12?). Doing so will allow you to continue determining the remaining digits!

• public int compareTo(BigInt other)
  This method should compare the called BigInt object to the parameter other and return:

  • -1 if integer represented by the called object is less than the integer represented by other

  • 0 if integer represented by the called object is equal to
    the integer represented by other

  • 1 if integer represented by the called object is greater than the integer represented by other

  The method should not modify the original objects. If the parameter is null, throw an IllegalArgumentException.

  See the section on algorithms below for guidance.

• public BigInt add(BigInt other)
  This method should create and return a new BigInt object for the sum of the integers represented by the called object and other. For example:

  BigInt val1 = new BigInt(1111111);
  BigInt val2 = new BigInt(2222);
  BigInt sum = val1.add(val2);
  System.out.println(sum);
  

  should print:

  1113333
  

  The method should not modify the original objects.

  Special cases:

  • If the parameter is null, throw an IllegalArgumentException.

  • If the result overflows—i.e., if it requires more than MAX_SIZE digits—you should throw an ArithmeticException (not an IllegalArgumentException).

  See the section on algorithms below for guidance.

• public BigInt mul(BigInt other)
  This method should create and return a new BigInt object for the product of the integers represented by the called object and other. For example:

  BigInt val1 = new BigInt(11111);
  BigInt val2 = new BigInt(23);
  BigInt product = val1.mul(val2);
  System.out.println(product);
  

  should print:

  255553
  

  Here again, the method should not modify the original objects, and you should throw an IllegalArgumentException if the parameter is null and an ArithmeticException if the result overflows.

  See the section on algorithms below for guidance.

• public int[] getDigits() – Returns a reference to the the internal digits array of the object.

Algorithms
The algorithms for manipulating these big integers are simply computational versions of the procedures that we would use to add, compare, or multiply integers “on paper”.

For example, to add two arrays of digits, we must go from right to left (i.e. least significant digit to most significant digit) adding the digits and keeping track of the carry. For example, to add 57339 to 4598, the process looks something like this:

carry:           1   0   1   1     
            -----------------------+
       ...   0 | 5 | 7 | 3 | 3 | 9 |
            -----------------------+
            -----------------------+
       ...   0 | 0 | 4 | 5 | 9 | 8 |
            -----------------------+
            -----------------------+
sum:   ...   0 | 6 | 1 | 9 | 3 | 7 |
            -----------------------+

Note that addition will result in overflow (creating a number with more than 20 digits) if you need to add the digits in position 0 of the two arrays and if their sum plus any incoming carry value produces a value that is greater than or equal to 10.

We encourage you to:

• Go through a similar analysis using concrete cases to determine the algorithms for comparing and multiplying BigInt objects.

• Consider how you could use the numSigDigits field to assist you in the execution of your algorithms.

• For the sake of efficiency, consider writing a private helper method that checks if a BigInt object represents the number 0 or 1. If you know that one of the operands in a multiplication or addition expression is zero, how would that help you? If you know that one of the operands in a multiplication expression is one, how would that help you?

Submitting your work for Part II

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

You should submit only the following files:

• BigInt.java

Make sure that you do not try to submit a .class file or a file with a ~ character at the end of its name.

Here are the steps:

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

2. Click on the name of the assignment (PS 4: Part II) 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.)

3. 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.

4. Click the Upload button.

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

6. 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.

7. 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.

8. 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.