CSE 160
HW #4
Due Tuesday, March 3, 2009


Reading: Read Ch 4 in the Objects First text.  Work along with it, using BlueJ. Also read about the JavaDoc system in the appendix on pp. 456-458, and peek ahead to the JavaDoc material on pp. 120-130 and 146-147 in Chapter 5.
                 
Lab Feb 25:

TBA


HW #4 Due at start of class Tuesday:

A) Improvements to the JukeBox game

1) Write comments for all your classes in JavaDoc format, including all fields, constructors, and all methods. View the generated web pages and make sure there is sufficient information there for someone to understand how to use your code.

2) Look at the JavaDocs for the class ArrayList, especially the add(), get(), remove(), size(), and clear() methods. Using an ArrayList, modify your Pocket class to hold multiple balls. Balls are received one at a time and collected in the pocket. Your isFull() method should return true only when the pocket is full. When a pocket's empty() method is called, all of its balls should be sent to the appropriate outlet, starting with the most recently received, using some sort of for or while loop. Test that your switch works properly with pockets of size 1, 2, or 3.

3) Review the material on arrays, starting on p. 105. Rewrite the Pocket class to hold the balls in an array of type Ball[] instead of an ArrayList. It should have exactly the same external behavior, i.e., when other objects use a pocket's constructor and receive(), isFull() and empty() methods, there should be identical behavior whether you used an ArrayL:ist or an array in implementing the Pocket class.

4) When all the above is working, modify your Game class to have four switches and all the necessary tubes and pockets for the online game level 11, which has some pockets of each size: 1, 2, and 3. You can test it by seeing if a random sequence of reds and blues produces the same score in your game as in the online game.

5) Pack your project folder (with the array implementation of Pocket) as a zip file and email it as an attachment to the TA.

B) Big Numbers

Look up the JavaDocs for the Integer class and read page 254 in the text, about Integer objects and the int primitive type. We will create an ArrayList of Integers, but you can think of them as ints because (in Java 1.5) an int is automatically converted to an Integer when put into a collection. Review the arithmetic operators in Appendix D; note that "/" does integer division (dropping any remainder) and "%" is the "modulo" operator which gives the remainder.

The primitive int and Integer types provided by Java have only limited width. Values of type byte are eight bits in width, values of type char or short are sixteen bits in width, values of type int or Integer are thirty-two bits in width, and values of type long are sixty-four bits in width. For some applications, fixed-precision values are an inconvenience: what you would rather have is a data type capable of representing integer values of arbitrarily many bits. Such a data type is traditionally called a "bignum".

In this lab, you are to implement a class Bignum, whose objects represent arbitrary-precision non-negative integers. Bignum objects can be implemented using lists; in particular, you can represent a Bignum by the list of its digits, say, in base 10. For example, the value 123 could be represented by a list containing Integer objects with values 1, 2, and 3. Or, you might find it more convenient to list the digits in reverse order, so that 123 is represented by the list of values 3, 2, 1.

Your Bignum class should have the following skeleton, providing at least the methods indicated below.

import.java.util.ArrayList;

public class Bignum {
  public Bignum(int intValue);
  public Bignum add(Bignum num);
  public Bignum mul(Bignum num);
  public Bignum exp(int n);
  public String toString();
  }

The constructor creates a Bignum having a specified integer value. The toString method should create a printable base-10 representation of a Bignum value. 

The add method adds the Bignum "num" to "this" Bignum, and returns a Bignum representing the sum. The  mul method behaves similarly, implementing multiplication. Note that Bignum objects should be immutable: once a Bignum object has been created, there should be no way to change the value it represents. So add and mul return a new value, rather than modifying "this" Bignum.

Your code for add and mul can work by simulating the "grade-school" algorithms you learned as a child. For example, you can implement add by working one digit at a time starting from the least-significant (i.e. the "ones") digit and progressing toward the most-significant digit, keeping track of the current "carry" as you go. You may want to make an accessor to get the kth digit of a Bignum. For mul, you might find it helpful to first implement a private method for multiplying an arbitrary Bignum by a single digit. You may want to make a shiftLeft(k) method which return this times 10 to the kth power.You can then implement mul by performing several such multiplications by single-digits and using add to add up the results. The exponentiation method takes an int argument, as we will not need large exponents, and can work by repeated multiplication.

You can test your class with a Test class that has a constructor similar to this:

    public Test()
    {
        Bignum x = new Bignum(100004);       // a sample product
        Bignum y = new Bignum(33);
        Bignum z = x.mul(y);
        System.out.println(x.toString() + " * " + y.toString() + " = " + z.toString());
       
        for (int i=0; i<=50; i++) {          // a table of powers of two
          System.out.println(i + ": " + new Bignum(2).exp(i).toString());
          }
         
        System.out.println(new Bignum(987).exp(23).toString());  // 987^23    
     }

Once you have coded and tested your Bignum class, use it to compute and print out the exact value of 987 to the power 23.  Include the answer in your email to the TA with your Bignum jar file.