8:00 Quiz 7

One-page version suitable for printing.

Statistics:

mean     22.974 (896.000/39)
stddev   4.780
median   24.000
midrange 19.000-26.000

#  avg
1  5.31 /  7
2  4.13 /  8
3 13.54 / 15

Question 7-1

[7 pts] Draw a recursion tree representing the recursive calls made to f in the course of computing the value of f(11) using the following method.

public static void f(int n) {
  if(n <= 1) {
    return 1;
  } else if(n % 2 == 0) {
    return 2 * f(n / 2);
  } else {
    return f((n - 1) / 2) + f((n + 1) / 2);
  }
}

Solution

Question 7-2

[8 pts] Consider the following method.

public static void run() {
    int n = IO.readInt();
    for(int i = n; i > 0; i /= 2) {
        IO.print(i % 2);
    }
}

Solution

Question 7-3

[15 pts] Define a class PigPen for tracking the number of pigs in in a pen. It should support the following methods.

PigPen(int pigs)
(Constructor method) Constructs an object representing a pig pen containing pigs pigs.

boolean isEmpty()
Returns true if there are no pigs in the pen.

void pigEnters()
Adds one to the number of pigs in the pen.

void pigExits()
Subtracts one from the number of pigs in the pen.

For example, if you defined this class properly, I should be able to write the following class to test it.
public class PigPenTest {
    public static void run() {
        PigPen pen = new PigPen(2);
        pen.pigExits();
        IO.println(pen.isEmpty()); // prints ``false''
        pen.pigExits();
        IO.println(pen.isEmpty()); // prints ``true''
        pen.pigEnters();
        IO.println(pen.isEmpty()); // prints ``false''
    }
}

Solution