Problem Set 3

This problem set is due in two parts, please see below for specific due dates.

General Guidelines

• In your work on this and all subsequent problem sets, you may not use data structure classes such as ArrayList or any of Java’s built-in collection classes unless a problem explicitly states that you may do so. We are learning to write Java classes from the ground up and you must learn how these classes are built; however, you are free to use (unless specifically directed otherwise) the basic classes: String, Character, Scanner, and Math; You may also use the toString(...) method from the Arrays class if you wish (EXCEPT when specifically forbidden to do so).
• You may freely use code from the class web site, assigned readings, or lecture (unless specifically directed otherwise) as long as you cite the source in your comments; but you may NEVER use code from the web or other students’ programs—this will be considered plagiarism and penalized accordingly.
• In addition, 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 submit your work following the procedures found at the end of the assignment.

Part I

60 points total, due by 11:59 p.m. on Sunday, February 17, 2019

Problem 1: Inheritance and polymorphism

15 points total; individual-only

Put all of your work for this problem in a plain-text file named ps3pr1.txt.

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

• Class Gee 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:

  • integer fields x and y
  • a non-static method called foo() that takes no parameters and returns a String
  • its own toString() method that overrides the inherited one.

• Class Zee extends Gee. In addition to the members that it inherits, it has:

  • a String field called par
  • a non-static method called moo that takes an integer and returns a String
  • its own toString() method that overrides the inherited one.

• Class Yee extends Gee. In addition to the members that it inherits, it has:

  • an integer field z
  • its own toString() method that overrides the inherited one.

• Class Tee extends Yee. In addition to the members that it inherits, it has:

  • a String field called bar
  • an equals method 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.

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

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

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 these classes, although doing so is not required.

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

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

3. Consider the following code fragment:

   Tee t1 = new Tee();
   System.out.println(t1.equals(t1));
   System.out.println(t1.foo());
   System.out.println(t1);
   System.out.println(t1.moo());
   

   Each of the print statements in this code fragment displays the result of a method call. (This includes the third print 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 Tee class nor inherited from a superclass of Tee.

   Copy the table below into your ps3pr1.txt file, and complete it with appropriate information about each of the method calls. We have filled in the first row for you.

                 |              | will the call | if the call compiles,   
     which print | which method | compile       | which version of the    
     statement   | is called    | (yes/no)?     | method will be called?  
   =======================================================================
   | first one   | equals()     | yes           | the Tee version        |
   +-------------+--------------+---------------+------------------------+
   | second one  |              |               |                        |
   +-------------+--------------+---------------+------------------------+
   | third one   |              |               |                        |
   +-------------+--------------+---------------+------------------------+
   | fourth one  |              |               |                        |
   +-------------+--------------+---------------+------------------------+
   

4. Now imagine that you want to add a non-static method to the Yee class. It should be called yow(), it should take no parameters, and it should return the sum of the integer fields in the called Yee object. Add a full definition of that method to your ps3pr1.txt file. Make sure to take into account the fact that the classes employ proper encapsulation.

5. 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.     Yee y = new Tee();

   2.     Zee z = new Gee();

   3.     Tee t = new Zee();

   4.     Gee g = new Tee();

Problem 2: Histogram

25 points total; pair-optional

This is the only problem in this 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.

For this problem, write a program Histogram.java which implements a static class named Histogram. This class will provide a series of static methods which will allow a client to produce and display a histogram of a series of floating point values.

 a <= x <= b and

 a < x <= b.

[0..10]: ** 
(10..20]: *** 
(20..30]: * 
(30..40]:  
(40..50]: **** 
(50..60]: ** 
(60..70]: ** 
(70..80]: ** 
(80..90]: ** 
(90..100]: **

Begin by downloading the file: Histogram.java, which sets-up the skeleton of your class.

A few sample runs are shown in the screenshots below. You should follow these as closely as possible as a guide to develop your program. However, we will specifically be testing for the accuracy of the resulting histogram.

1. Write a method calulateHistogram that computes the histogram. This method should accept the array of numbers as an input argument, as well as how many number were entered. The method then should compute and return the array that represents the histogram.

   public static int [] calculateHistogram( double [] numbers, int numEntered ) {
       ....
   
       // This method must determine the appropriate bin of the 
       // histogram to update by using a loop. To be clear,
       // you may NOT just explicitly account for all  
       // possibilities, e.g., the following is a bad solution:
   
       if(number <= 10.0) {           // VERY BAD SOLUTION
           ++histogram[0];
       }
       else 
       if(number <= 20.0) {
           ++histogram[1]; 
       }
   
       etc.
   
   }
   

2. Write a method getHistogramAsString to construct a String representation of the histogram (similar to the toString method of an array).

   public static String getHistogramAsString( int [] histogram ) {
       ....
   
       // This method must also use a loop that iterates 
       // over the histogram array to form the string
       // representaion of it.
   
       // The histogram can be visualzed as a series of
       // buckets, where each bucket represents one range
       // of the histogram:
          [0..10]: **** 
          (10..20]: ** 
          (20..30]: *** 
          (30..40]: * ... ]
   
       // The string returned should only contain the string representation
       // of the histogram and no other verbeage. It should function
       // like the toString method of the Array class but specific to
       // creating a histogram.
   
       // You may want to create an instance of the
       // StringBuilder class to assist you in this method.
       // Follow the code in the method getHeaderAsString
       // as a guide.
   }
   

3. Write a method to determine if the inputs are in the legal range i.e. [0.0 .. 100.0]:

   public static boolean validInput( ... ) {
       ....
   }
   

4. Write a main method that controls the execution of your program. We will not mark your main method and you can edit it in any way you like. However, we suggest you follow the following recommended tasks:

   public static void main( ... ) {
   
       // Declare your variables
   
       // Invoke the method provided to produce a String which your program
       // can output to display the welcome message.
   
       // Populate the array of numbers through user input
       // Make sure to follow the guidelines specified above.
   
       // Invoke the function to calculate the histogram
   
       // Invoke the functon to produce a String representation of the histogram
   
       // Output the string representation
   
   }
   

5. Finally, but most importantly, you must store the maximum number of inputs (20) and the number of bins in the histogram (10) as final instance variables; you should NOT have the numbers 20 or 10 occur anywhere in your program except in the declarations of these variables. You MUST do this so that if you decide to change one of these, you don’t have the “multiple update” problem. Here is an example of what you should use:

   public class Histogram {
   
       public static final int MAX_NUMBERS = 20;  // maximum number of numbers to input
       public static final int NUM_BINS    = 10;  // number of bins in range [0..100]
   
       // You should also declare and initialize variables for:
       // UPPER_BOUND  to represent the largest possible number in the range
       // LOWER_BOUND  to represent the smalles possible number in the range
       // BIN_SIZE     how many different values fall into each bin
   
       public static void main(....) etc.
   

number of bins     size of bins
    10                10     i.e.,  [0..10], (10..20], ...., (90..100]
     5                20     i.e.,  [0..20], (20..40]  ...., (80...100]
     2                50     i.e.,  [0..50], (50..100]

Problem 3: Adding methods to the ArrayBag class

20 points total; individual-only

Begin by downloading the file ArrayBag.java and opening it in Ecplise or the IDE you are using.

Add the methods described below to the ArrayBag class, and then add code to the main() method to test these methods. You should not add any new fields to the class.

1. public int capacity()

   This method should return the maximum number of items that the ArrayBag is able to hold. This value does not depend on the number of items that are currently in the ArrayBag — it is the same as the maximum size specified when the ArrayBag was created. For example:

   > ArrayBag b1 = new ArrayBag(10);
   > ArrayBag b2 = new ArrayBag(20);
   > b1.capacity()
   10
   > b2.capacity()
   20
   > b1.add("hello");
   > b1.capacity()    // capacity doesn't change as items are added
   10
   

2. public boolean isEmpty()

   This method should return true if the ArrayBag is empty, and false otherwise. For example:

   > ArrayBag b1 = new ArrayBag(10);
   > b1.isEmpty()
   true
   > b1.add("hello");
   > b1.isEmpty()
   false
   

3. public boolean addAll(Object[] newItems)

   This method should attempt to add to the called ArrayBag all of the items found in the array newItems that is passed as a parameter, and it should return a boolean value indicating success or failure.

   • If there is enough room for all of the items to be added, the items should be added and the method should return true.

   • If there isn’t enough room for all of the items to be added, none of them should be added, and the method should simply return false.

   For example:

   > ArrayBag b1 = new ArrayBag(6);
   > String[] words = {"hello", "how", "are", "you?"};
   > b1.addAll(words)
   true
   > b1
   > {hello, how, are, you?}
   > String[] words2 = {"not", "bad", "thanks!"};
   > b1.addAll(words2)
   false
   > b1
   > {hello, how, are, you?}
   > String[] words3 = {"not", "bad!"};
   > b1.addAll(words3)
   true
   > b1
   > {hello, how, are, you?, not, bad!}
   

   For full credit, you should take full advantage of the existing ArrayBag methods.

4. public ArrayBag merge(ArrayBag other)

   This method should create and return an ArrayBag containing one occurrence of any item that is found in either the called object or the parameter other. For full credit, the resulting bag should not include any duplicates. Give the new ArrayBag a maximum size that is the sum of the two bag’s maximum sizes.

   For example:

   > ArrayBag b1 = new ArrayBag(10);
   > String[] letters1 = {"a", "a", "b", "d", "f", "f", "f", "g"};
   > b1.addAll(letters1);
   > ArrayBag b2 = new ArrayBag(8);
   > String[] letters2 = {"a", "b", "c", "d", "d", "e", "f"};
   > b2.addAll(letters2);
   > ArrayBag b3 = b1.merge(b2);
   > b3
   {a, b, d, f, g, c, e}    // order doesn't matter!
   > b3.capacity()
   18
   > b3.numItems()
   7
   > b1     // make sure original bags are unchanged
   {a, a, b, d, f, f, f, g}
   > b2
   {a, b, c, d, d, e, f}
   

   For full credit, you should take full advantage of the existing ArrayBag methods. They will make your job much easier!

   Special cases:

   • If one of the bags is empty, the method should return an ArrayBag containing one occurrence of each item in the non-empty bag.
   • If both of the bags are empty, the method should return an empty ArrayBag.
   • If the parameter is null, the method should throw an IllegalArgumentException.

Part II Designing a Custom Object Class

Problem 4: Big Int Library: a Class based solution for working with large integers

40 points total; individual only, due by 11:59 p.m. on Friday, Friday 22, 2019, no late submissions accepted

Overview

In this problem you are going to create a class to solve the problem that in Java, the int data type can only represent integers in the range [-2,147,483,648 . . 2,147,483,647]; this is not big enough for storing, for example, the population of Earth (7.125 billion) or computing factorials for large values of n.

The Java libraries contain a class BigInteger to solve this problem, but we are going to write our own class, BigInt, with only a subset of the functionality of the Java class.

Representation of Big Integers by Arrays of Digits

We will represent our big integers by using arrays of integers, where each array entry (i.e. element of the array) represents an individual digit of a big integer, Example:

public static final SIZE = 20;    // a constant in the BigInt class to indicate the
                                  // maximum size of a BigInt array
     ....

// use the constant variable SIZE to declare the size of the array of digits
public int digits[] = new int[BigInt.SIZE];

An integer such as 57431 is represented by an array A containing integers which are in the range [0 – 9] (i.e., digits) with as many leading zeros as necessary to fill up the entire array, Example:

00000000000000057431

would be presented as

               0   1   2              14  15  16  17  18  19   
             +-----------           ------------------------+
    digits:  | 0 | 0 | 0  .......   | 0 | 5 | 7 | 4 | 3 | 1 |     
             +-----------           ------------------------+

Note that the elements in the array must all be single digits and that the last entry of the array represents the least significant digit of the integer.

The BigInt array that represents the value for 0 will have SIZE-1 leading 0’s and the last digit will be a significant digit, not a leading 0.

We will not represent negative integers, but would be interesting for you to think how we could.

We will also declare a special BigInt object NaBI (Not a Big Int) for error checking purposes. This array will consist of a -1 in slot 0, with the remaining values set to 0:

               0   1   2              14  15  16  17  18  19   
             +-----------           ------------------------+
      NaBI:  |-1 | 0 | 0  .......   | 0 | 0 | 0 | 0 | 0 | 0 |     
             +-----------           ------------------------+

The Methods of the BigInt Class:

public BigInt() -- Constructor to create a BigInt object of NaBI.

public BigInt(int [] ) -- Constructor that creates a BigInt object from 
   an array passed. The array should be checked that it is a valid representation 
   of a BigInt. If not the object should be constructed as NaBI.

public BigInt(int n) -- Constructor that convert the integer n into 
   a BigInt object; if n < 0, then the object should be constructed as NaBI;
   note that n won't overflow the array, since it's an int.

public BigInt(String s) -- Constructor that converts the String s into a 
   BigInt object; if s does not represent a legal integer (i.e., contains a 
   character other than '0' .. '9' or is longer than SIZE characters) 
   object should be constructed as NaBI.

public String toString() -- Instance method that returns a String 
   representation of the big integer object *with leading zeros suppressed*. If
   any member of the object is NOT a digit (e.g., is negative or > 9) 
   return the string "NaBI".

public int compareTo(BigInt B) -- Compare two big 
   integer objects and return -1, 0, or 1, depending on whether

   A < B, A == B, or A > B, respectively.

public BigInt add(BigInt B) -- Add two big integers and 
   return a new BigInt object representing their sum; if the result overflows, i.e., 
   contains more than SIZE digits, return NaBI.

public BigInt mul(BigInt B) -- Multiply two big integer objects and
   return a new BigInt object representing their product; if the result overflows, i.e.,
   contains more than SIZE digits, return NaBI.

Algorithms

The algorithms for manipulating these big integers are simply adaptations of the rules for addition and comparison of integers. For example:

To add two arrays of digits, we must go from right to left (i.e. least significant to most significant digit) adding the digits and keeping track of the carry:

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

Note that the addition will result in an overflow (create a number larger than 20 digits) if the sum of the left-most two digits is larger than 10, in which case you should return NaBI.

We encourage you to go through a similar analysis to determine the algorithm for multiplying two big integers.

Completing your Solution

Begin with the template code BigInt.java. To implement your solution complete each method in the template BigInt.java. Note that this template will not compile because of missing return statements in the template methods. You can either comment out all the methods, except the method you are working on or put in dummy return statements in all the methods to force the program to compile.

It is strongly recommended that you code and test each method one at a time. Do not try and write all the methods first and then compile and test your program.

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;

Follow the instructions and submit the following files:

• ps3pr1.txt
• Histogram.java; if you worked with a partner on this problem, make sure that you each submit a copy of your joint work, and that you include comments at the top of the file specifying the name and email of your partner
• Arraybag.java
• BigInt.Java