8:00 Quiz 7

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);
    }
}

a. Suppose we were to run the program and type 11. What would the program print?
b. Suppose we were to type some number n. In terms of n, how much time does the above method take? Use Big-O notation to express your answer, and provide the tightest bound that you can.

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