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


Goals of this homework:

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.

How to hand in your work: instructions, upload page. Make sure to name your partner (if you had one) at the top of your Readme file.

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


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

Answer in your Readme file:
  1. Figure out the runtime of the add method by studying the source code. Specifically, if two numbers a and b are represented as Russian dolls, does a.add(b) take time O(a), O(b), O(a+b), O(ab), or something else? Explain.
  2. Figure out the space requirements of the add method by studying the source code. Specifically, if two numbers a and b are represented as Russian dolls, does a.add(b) use space O(a), O(b), O(a+b), O(ab), or something else? Explain.

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

Answer in your Readme:
  1. Try a.add(b) for various values of a and b. Use newWork to report the amount of work done in each case (not counting the work to create a and b!). Use these results to guess an exact formula (without big-Oh notation) for the return value of newWork in terms of a and b. Did your big-Oh answer in question 1 correctly describe this formula?
  2. Same question for newSpace. Did your big-Oh answer in question 2 correctly describe this formula?

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!

Answer in your Readme:
  1. Using big-Oh notation, what is the runtime of equals? You may wish to check this using newWork.

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.

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

  1. What is the asymptotic (big-Oh) runtime of a.multiply(b) in terms of a and b? Explain why this is true theoretically (based on what the code has to do), and also support your answer with several results from newWork.
  2. Same question for a.multiplySlow(b). This is the most interesting question on the assignment!

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:

Once RussianDoll compiles again, try the NumericTest class to make sure that RussianDoll objects can be treated as Numeric and act as expected. Extend NumericTest to test the code until you are sure everything is working. Answer in your Readme:
  1. This assignment has said several times that java.math.BigInteger also implements Numeric. However, Java doesn't know that! For example, we can't store a BigInteger in a Numeric variable.

    Since we didn't write the BigInteger class, we can't just add implements Numeric to its first line (the way we did for RussianDoll). So how can we easily create a kind of BigInteger class that does implement Numeric? (You might want to try your answer out!)

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.

Answer in your Readme:
  1. What did newWork and newSpace return for the above code, both before and after the modification? Explain why you got exactly the numbers you got.
  2. Your classmate says that the modification will always save memory. Give a counterexample.
  3. The modification should generally speed up the arithmetic methods (addition, subtraction, multiplication, division), because looking up rd.outer is faster than creating a new doll with new RussianDoll(rd). But will it actually improve the asymptotic complexity (big-Oh formula) for any of the arithmetic methods? Defend your answer.
  4. Note that with the modification, two equal dolls are always ==. If equals is changed to take full advantage of this fact, what is the asymptotic (big-Oh) runtime of a.equals(b)? Compare to your answer to question 5.

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.

In addition to handing in your modified add as part of your RussianDoll.java, you should answer the following in your Readme:
  1. Give the asymptotic runtime and space requirements of your new add.
  2. The above runtime and space requirements should improve on question 1. Nonetheless, is there any reason to believe that new add is sometimes slower than the old one? If so, what is the motivation for using the new add?

Jason Eisner - jason@cs.jhu.edu - $Date: 2004/02/02 19:33:41 $