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

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.

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.

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''
    }
}

Solutions

Solution 7-1

     11
   /    \
  5      6
 / \     |
2   3    3
|  / \  / \
1  1 2  1 2
     |    |
     1    1

public class PigPen {
    private int count;

    public PigPen(int pigs) {
        count = pigs;
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public void pigEnters() {
        count++;
    }

    public void pigExits() {
        count--;
    }
}