600.226 Data Structures (Spring 2004 - Prof. Eisner)

Homework 2 ... due 4pm Friday 13 Feb 2004

Parts of this assignment require you to understand big-Oh notation (which will be covered in class on Wed 2/4).

Summary

Goals of this homework:

• Practice with recursive classes and recursion, and static variables.
• Gaining comfort with abstraction: Russian dolls can represent numbers, and a single interface (Numeric) can have different implementations.
• Analysis of simple algorithms.
• Practice the strategy of storing data that you might need later.
• Finally, some indirect exposure to linked lists, which our implementation resembles.

Collaboration policy for this homework: You must follow the CS Department Academic Integrity Code, except that for this homework, you may optionally work with one other student in the class. If you do so, you must say who your partner was at the top of your Readme file, and both of you will receive the same grade for the assignment.

What to hand in (all packaged up in a zip or tar file):

• Your commented code:
  • RussianDoll.java. The completed version you hand in must implement the Numeric interface; we'll use that interface to test your code. Our tests will also assume that you have implemented public static methods valueOf and newWork, and a public instance method multiplySlow.
  • NumericTest.java, as modified by you, showing that you did an adequate job of testing. (You could also put most of your test code in RussianDoll.java if you prefer.)
  • Numeric.java. This is given to you and you don't need to change it.
  • A doc subdirectory containing HTML documentation that you have generated with the command javadoc -private -linksource -d doc *.java. The graders will look at this documentation, so you should provide javadoc comments for all of your methods, including private ones.

  Again, please follow the style guidelines in section 1.9.2 of the textbook.

• A Readme file that contains your answers to miscellaneous questions on the homework (i.e., answers that don't go in any other file). Usually these are English paragraphs or small fragments of code.

Introduction

We have already begin discussing in class how an abstract data type can be implemented in multiple ways. For example, stacks can be implemented using either arrays or linked lists.

Similarly, there are multiple ways to implement the natural numbers (0, 1, 2, 3, ...). Modern computers typically use a binary representation. (Of course, Java's built-in integer type doesn't really implement the natural numbers -- with 32 bits it can only represent numbers up to 2147483647. But the java.math.BigInteger class basically uses an array of bits; for larger numbers it just uses more bits.)

The Russian dolls that we developed in class can also be made to represent natural numbers, essentially in unary notation. This representation is much simpler but also much less efficient, so you can guess that it was invented by a mathematician (Giuseppe Peano in 1889) rather than an engineer. His main point (published in Latin, just for kicks) was that if God had not seen fit to give us integers, we could have built them out of something else.

In this assignment, you will do just that and build integers out of Russian dolls - complete with addition, subtraction, multiplication, and division. You'll find out just how inefficient this implementation is, both by using big-Oh notation and by actually measuring it. Finally, you'll make it a bit more efficient.

The Files

Your job in this assignment is to finish the partly written RussianDoll class. By the time you are done, it will be an implementation of this supplied Numeric interface. (Other implementations of that interface include java.math.BigInteger.) To test that you are correctly implementing the interface, you can write a test class that manipulates Russian dolls through that interface; we have supplied a small NumericTest to get you started.

Copy the above three files from this source directory. Start by reading the source code files and their documentation. (If you like, you could also look at the successive versions we developed in class.)

Type Conversions

All the methods that do arithmetic on Russian dolls should only use Russian dolls. But first, add two methods to the RussianDoll class that convert between Russian dolls and longs:

  public long longValue() {
    ...
  }

  public static RussianDoll valueOf(long val) {
    ...
  }

You should implement one of them using recursion and the other using iteration - either way around, as you prefer. The add or toString method illustrates how to use recursion.

The expected behavior of these methods is documented in the Numeric interface (including the comments at the top). Make sure that they throw ClassCastException if the conversion can't be accomplished, e.g., valueOf(-2), or rd.longValue() where the appropriate return value exceeds Long.MAX_VALUE. (Note: ClassCastException, like the other subclasses of RuntimeException, is an unchecked exception, meaning that you don't have to include "throws ClassCastException" in the method signature.)

You should not use these methods to implement any of the other methods below, although they will be useful to help you test those methods. The other methods must be implemented entirely with Russian dolls without using any of Java's built-in numeric types (byte, short, integer, long, float, double, BigInteger, etc.) in any way, not even as array indices.

Complexity of Addition

Now you will actually check your answers by instrumenting the source code. This means making the code keep track of what it is doing. Implement the following methods in RussianDoll:

  /** Returns the total amount of work done by this class since
   * the last time this method was invoked.  The amount of
   * work is measured by the total number of calls to the 
   * bigger and smaller methods, no matter who called them
   */
  public static long newWork() {
     ...
  }

  /** Returns the total amount of space allocated by this class
   * since the last time this method was invoked.  The amount of space
   * is measured by the total number of calls to constructors (not
   * including the call that created ZERO).  Possibly some of the
   * space was released along the way.
   */
  public static long newSpace() {
    ...
  }

Hint: Start by defining a private static field that is incremented on each call to bigger or smaller ... Reset that field to 0 sometimes ...

Tip of the day: In answering the above questions, did you find yourself cutting-and-pasting code? Rather than write new code for every pair of numbers that you want to try adding, it is easier to write a new method that you can call as something like addTest(30,40), and which prints the work and space needed for that addition. Then it's easier to read the code, easier to add new tests, and it's easier to change the way the test works or prints its results.

Comparison Methods

Add equals and compareTo methods to RussianDoll. Again, the desired behavior is documented in the Numeric interface (although for now, you may assume that the argument is a RussianDoll, not an arbitrary Object). You may use either iteration or recursion, but recursion is more elegant.

Remember that you are not allowed to use Java's built-in numeric types (except for the return value of compareTo). As always, if you find yourself writing duplicate code, reorganize things to avoid this!

Arithmetic Methods

Implement the subtract, multiply, and divideAndRemainder methods with the behavior documented in the Numeric interface. For now, assume that they take a RussianDoll argument and return a RussianDoll. Either recursion or iteration is okay; I think recursion is easier for subtract and multiply, whereas iteration is easier for divideAndRemainder. Test the methods to your satisfaction.

• subtract can be implemented in a manner similar to compareTo.
• multiply can use repeated addition, exactly as add used repeated increments.
• divideAndRemainder can use repeated subtraction.
• Tip: Earlier I suggested that you write an addTest method that you could call from main. You may also want to write subtractTest, multiplyTest, etc. As much as possible, avoid duplicating code among these test functions.

Because the RussianDoll class can't represent negative numbers, we have to decide what a.subtract(b) does when a < b. Your implementation should return ZERO in this case. This decision is consistent with our earlier decision that ZERO.smaller() == ZERO.

Remember from earlier in this homework that add has asymmetric time and space requirements. That is, a.add(b) might be less efficient than b.add(a), even though both give the same answer. Since multiply is implemented by repeated addition, it matters whether multiply calls add efficiently or inefficiently.

To see how much this matters, create a second version of multiply, where instead of x.add(y) you do y.add(x) (for whatever objects x and y you are adding). Call the fast version multiply and call the slow version multiplySlow. (Warning: Make sure that multiplySlow recurses by calling multiplySlow, not multiply.)

Implementing the Numeric interface

Now the RussianDoll class almost implements the Numeric interface. Augment the first line of RussianDoll.java to make this intention explicit:

  public class RussianDoll implements Numeric {

Now fix RussianDoll.java so that it compiles again. That means the compiler agrees that RussianDoll is a valid implementation of Numeric. Some things you may have to do:

• Numeric.add (for example) is an abstract method that can be called with any Numeric argument:

    public Numeric add(Numeric val);

  If RussianDoll implements Numeric, then we must be able to call RussianDoll.add with any Numeric argument. So the signature we gave you,

    public RussianDoll add(RussianDoll val)

  is not enough; you actually need to change it to

   
    public RussianDoll add(Numeric val)
  

  The method should simply cast val to a RussianDoll before working with it. If val is some other kind of Numeric, like a BigInteger, trying to cast it to RussianDoll may throw a ClassCastException -- which the Numeric interface says is an appropriate response if someone tries to add two Numeric objects from different subclasses.

• It gets worse. For some brain-dead reason, since Numeric.add returns a Numeric,

    public Numeric add(Numeric val);

  Java thinks that the RussianDoll.add method that implements it must have exactly the same signature, and explicitly return a Numeric. I am completely baffled by this -- it should be enough to return RussianDoll, since after all that is a kind of Numeric. But this obvious feature (called "covariant return types") isn't coming until Java 1.5; there are many complaints on the web.

  So unfortunately, the compiler will only compile your RussianDoll class as an implementation of Numeric if you further change

    public RussianDoll add(Numeric val)
  

  to

    public Numeric add(Numeric val)  // can still return a RussianDoll
  

  in your RussianDoll class. Similarly for several other methods. This requires a few other changes in RussianDoll.java, since now the result of a.add(b) is a Numeric, and cannot be assigned to a RussianDoll variable without an explicit cast.

• Just as RussianDoll.add must be able to apply to any Numeric argument, the RussianDoll.compareTo method must be able to apply to any Object argument. Again, it should simply try to cast this argument to RussianDoll, at the risk of throwing a ClassCastException if this fails.

• Remember that RussianDoll.subtract behaves in a non-obvious way that could not be predicted from the documentation of Numeric.subtract. So make sure to document this behavior at RussianDoll.subtract. (Why would it be a bad idea to document it at Numeric.subtract?)

Saving Space and Time

Let's close with a neat trick.

In general, we should try to avoid calling new: it's relatively slow and it uses up memory. For example, bigger is more wasteful than smaller because it calls new. But our RussianDoll class seems to call new more often than it has to. Consider the following code:

/* This code should be put at the top of main. */

RussianDoll rd1 = RussianDoll.valueOf(500);  // a representation of 500
Numeric rd2 = RussianDoll.valueOf(25).multiply(RussianDoll.valueOf(20));  
                                             // builds a completely separate representation of 500
RussianDoll rd3 = RussianDoll.valueOf(501);  // doesn't contain either rd1 or rd2
RussianDoll rd4 = RussianDoll.valueOf(499);  // not contained in either rd1 or rd2

System.out.println("Work: " + newWork() + " Space: " + newSpace());   

We'd really prefer the four values above to share space in memory. Then we'd only need to call new about 500 times, not about 2000 times. In general, there should be a unique doll representing 499, which is nested inside the unique doll representing 500, etc.

How might we achieve this? A first thought is for the RussianDoll class to maintain a static array that maps 499 to the unique 499 doll, etc. However, then we'd have to do Java integer arithmetic to compute the array indices, whereas we are trying to build our own integers.

The right solution is for each RussianDoll instance rd to have an outer field as well as an inner field. If rd is the unique doll representing the number n, then rd.outer should store the unique doll representing n+1, or null if that doll hasn't been created yet.

This is an example of a key strategy for data structures: store now what you will need again later! This is sometimes called "trading space for time." If the original RussianDoll class resembled a singly linked list, the modified one resembles a doubly linked list. Both doubly linked lists and our improved Russian dolls store the reverse pointers in order to save time later on.

Modify the RussianDoll class in this way, so that there is at most one doll representing each number. You should still count bigger as doing work, but you should only count it as using space if it calls new. Try running the code above both before and after your modification.

Extra Credit (optional)

We have noted that add has asymmetric runtime. So if you know which of a and b is bigger, then you know whether a.add(b) or b.add(a) is faster. But in general, you probably won't know this ahead of time.

For extra credit, can you modify the implementation of add to solve this asymmetry? Your implementation should be fast whenever either a or b is small, even if the other addend is incredibly large.