1.12: Exercises

The code for this chapter is in the ch10 directory of ThinkJavaCode. See [Section 0.4] for instructions on how to download the repository. Before you start the exercises, we recommend that you compile and run the examples.

Exercise \(\PageIndex{1}\)

The point of this exercise is to make sure you understand the mechanism for passing objects as parameters.

1. For the following program, draw a stack diagram showing the local variables and parameters of main and riddle just before riddle returns. Use arrows to show which objects each variable references.
2. What is the output of the program?
3. Is the blank object mutable or immutable? How can you tell?

public static int riddle(int x, Point p) {
    x = x + 7;
    return x + p.x + p.y;
}

public static void main(String[] args) {
    int x = 5;
    Point blank = new Point(1, 2);

    System.out.println(riddle(x, blank));
    System.out.println(x);
    System.out.println(blank.x);
    System.out.println(blank.y);
}

Exercise \(\PageIndex{2}\)

The point of this exercise is to make sure you understand the mechanism for returning new objects from methods.

1. Draw a stack diagram showing the state of the program just before distance returns. Include all variables and parameters, and show the objects those variables refer to.
2. What is the output of this program? (Can you tell without running it?)

public static double distance(Point p1, Point p2) {
    int dx = p2.x - p1.x;
    int dy = p2.y - p1.y;
    return Math.sqrt(dx * dx + dy * dy);
}

public static Point findCenter(Rectangle box) {
    int x = box.x + box.width / 2;
    int y = box.y + box.height / 2;
    return new Point(x, y);
}

public static void main(String[] args) {
    Point blank = new Point(5, 8);

    Rectangle rect = new Rectangle(0, 2, 4, 4);
    Point center = findCenter(rect);

    double dist = distance(center, blank);
    System.out.println(dist);
}

Exercise \(\PageIndex{3}\)

This exercise is about aliasing. Recall that aliases are two variables that refer to the same object.

1. Draw a diagram that shows the state of the program just before the end of main. Include all local variables and the objects they refer to.
2. What is the output of the program?
3. At the end of main, are p1 and p2 aliased? Why or why not?

public static void printPoint(Point p) {
    System.out.println("(" + p.x + ", " + p.y + ")");
}

public static Point findCenter(Rectangle box) {
    int x = box.x + box.width / 2;
    int y = box.y + box.height / 2;
    return new Point(x, y);
}

public static void main(String[] args) {
    Rectangle box1 = new Rectangle(2, 4, 7, 9);
    Point p1 = findCenter(box1);
    printPoint(p1);

    box1.grow(1, 1);
    Point p2 = findCenter(box1);
    printPoint(p2);
}

Exercise \(\PageIndex{4}\)

You might be sick of the factorial method by now, but we’re going to do one more version.

1. Create a new program called Big.java and write (or reuse) an iterative version of factorial.
2. Display a table of the integers from 0 to 30 along with their factorials. At some point around 15, you will probably see that the answers are not right anymore. Why not?
3. BigInteger is a Java class that can represent arbitrarily big integers. There is no upper bound except the limitations of memory size and processing speed. Take a minute to read the documentation, which you can find by doing a web search for “Java BigInteger”.
4. To use BigIntegers, you have to import java.math.BigInteger at the beginning of your program.
5. There are several ways to create a BigInteger, but the simplest uses valueOf. The following code converts an integer to a BigInteger:

   int x = 17;
   BigInteger big = BigInteger.valueOf(x);

6. Since BigIntegers are not primitive types, the usual math operators don’t work. Instead, we have to use methods like add. To add two BigIntegers, invoke add on one and pass the other as an argument.

   BigInteger small = BigInteger.valueOf(17);
   BigInteger big = BigInteger.valueOf(1700000000);
   BigInteger total = small.add(big);

   Try out some of the other methods, like multiply and pow.

7. Convert factorial so that it performs its calculation using BigIntegers and returns a BigInteger as a result. You can leave the parameter alone; it will still be an integer.
8. Try displaying the table again with your modified factorial method. Is it correct up to 30? How high can you make it go?
9. Are BigInteger objects mutable or immutable? How can you tell?

Exercise \(\PageIndex{5}\)

Many encryption algorithms depend on the ability to raise large integers to a power. Here is a method that implements an efficient algorithm for integer exponentiation:

public static int pow(int x, int n) {
    if (n == 0) return 1;

    // find x to the n/2 recursively
    int t = pow(x, n / 2);

    // if n is even, the result is t squared
    // if n is odd, the result is t squared times x
    if (n % 2 == 0) {
        return t * t;
    } else {
        return t * t * x;
    }
}

The problem with this method is that it only works if the result is small enough to be represented by an int. Rewrite it so that the result is a BigInteger. The parameters should still be integers, though.

You should use the BigInteger methods add and multiply. But don’t use BigInteger.pow; that would spoil the fun.