Computer Science 15-111 (Sections A & B), Spring 2007

Homework #3 (part 1)

Due: Fri 26-Jan-2007 at 10:30am (online submission).

SOLUTIONS

Place the written portions of the following problems in the file “hw3-written.txt” in your online submission of hw3.zip. Remember: Show your work!

Note:  The programs included here are not always written with ideal style, and as such are not always complete solutions.  They are meant to be complete enough for you to understand everything needed for your solutions.

1. In a few words of plain English, what does this method compute? Explain.
public static boolean foo(int[] x) {
for (int i=1; i<x.length; i++)
if ((x[i] <= 0) ||
(x[i-1] <= 0) ||
(x[i] / x[i-1] == 0))
return false;
return true;
}

The first two conditions test whether any element in x[] is negative. These will not trigger only if all the elements are positive. Thus, for the third condition, we assume x[i] and x[i-1] are positive. Since (x[i] / x[i-1]) uses integer division with truncation, it will equal zero so long as (x[i] < x[i-1]). This test is performed for every consecutive pair of elements in x[]. Thus, the answer: This method computes whether the array x contains positive integers sorted from least to greatest.

Check: The following code prints out: true false false
int[] a = { 1, 2, 3 };
int[] b = { 3, 2, 1 };
int[] c = { 3, 1, 2 };
System.out.printf("%b %b %b\n", foo(a), foo(b), foo(c));

2. Write a program, Median.java, that reads in a list of integers using scanner.nextInt(), ending when the sentinel -1 is entered, and prints out the median of the data (for a definition of median, see Wikipedia’s entry on “median”). Note that even for integral data, the median may be a float – for example, the median of { 2, 3 } is 2.5. Note that we discussed a static method in the Arrays class that is especially helpful here.

See Median.java.

3. Write a program, RemoveDuplicates.java, that reads in a list of integers ending with the sentinel -1, and then prints out the same numbers in sorted order, only with duplicates removed. For example, with user input underlined:
Enter data: 3 1 1 32 3 1 44 32 -1
Sorted data without duplicates: 1 3 32 44
Note that here, as in general, the sentinel is not considered part of the data.

See RemoveDuplicates.java

4. A “trace” of a program’s execution shows each method call, and each value returned, nesting and indenting these calls to indicate the call stack (thus, for example, any recursion that may occur). For example, consider the following method that computes the nth Fibonacci number:

public static int fib(int n) {
if (n < 2) return 1;
return fib(n-1) + fib(n-2);
}

Here is a trace of a call to fib(3), where arrows indicate return values:
fib(3)
fib(2)
fib(1)
--> 1
fib(0)
--> 1
--> 2
fib(1)
--> 1
--> 3
This trace clearly shows that fib is recursive, and for example that fib(3) calls fib(2), which in turn calls fib(1) and fib(0), after which fib(3) calls fib(1). This also shows that fib(1) is called twice. Once by fib(2) and again by fib(3).

If it helps, for instructional or debugging purposes, you can instrument a method to produce its own trace (though you must also be able to write traces by hand!). For example, here is an instrumented version of fib that produces precisely the trace above:
public static int fib(int n) {
return fib(n,0);
}

public static int fib(int n, int depth) {
// output method call, indented by recursive depth
for (int i=0; i<3*depth; i++) System.out.print(" ");
System.out.printf("fib(%d)\n",n);

// compute the result, recursing using the version
// that includes the depth in the signature
int result;
if (n < 2) result = 1;
else result = fib(n-1,depth+1) + fib(n-2,depth+1);

// output result, indented by recursive depth
for (int i=0; i<3*depth; i++) System.out.print(" ");
System.out.printf("--> %d\n",result);

// and return the result
return result;
}
Notice that this uses method overloading so that fib(int n) can still be called, although it is now just a wrapper for fib(int n, int depth) so that we can keep track of the depth of recursion, which we use to properly indent the output.

a. Trace a call to fib(4).
fib(4)
fib(3)
fib(2)
fib(1)
--> 1
fib(0)
--> 1
--> 2
fib(1)
--> 1
--> 3
fib(2)
fib(1)
--> 1
fib(0)
--> 1
--> 2
--> 5

b. Write a program, TracedFib1.java, which reads in a positive integer M and prints out a table showing, for each value N from 0 to M, the number of calls made to fib(1) while computing fib(N). For example, your program may run as follows (where user input is underlined):
Enter an upper bound for fib(1) tracing: 3
N calls to fib(1) while computing fib(N)
0 0
1 1
2 1
3 2
To write this program, include a static variable fib1calls, and in your main method, repeatedly set this variable to 0, call fib(n), then print out the resulting value of fib1calls. Now, in fib itself, test if n==1, and if so, increment fib1calls.

Here are the relevants portions:
private static int fib1calls;
public static int fib(int n) {
if (n == 1) fib1calls++;
if (n < 2) return 1;
else return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
//... //
for (int i=0; i<=max; i++) {
fib1calls = 0;
fib(i); // just ignore result
System.out.printf("%2d%11d\n",i,fib1calls);
}
}

c. Briefly explain why fib1calls must be a static variable.

Its value must be computed within fib(n), but its lifetime must extend beyond the call to fib(n). (Anything close to this explanation will suffice.)

Actually, we could do this without a static variable if we modified the signature of fib to take a MutableInteger (which we’d invent), as changes to object parameters are visible to the caller. To see this in action, check out this code, which runs the same as the previous code, but which does not have a static variable:

// First we define the following (very simple) class:
class MutableInteger {
public int value;
}

// Then we rewrite the excerpted code from above as such:

public static int fib(int n, MutableInteger fib1calls) {
if (n == 1) fib1calls.value++;
if (n < 2) return 1;
else return fib(n-1,fib1calls) + fib(n-2,fib1calls);
}

public static void main(String[] args) {
//... //
MutableInteger fib1calls = new MutableInteger();
for (int i=0; i<=max; i++) {
fib1calls.value = 0;
fib(i,fib1calls); // just ignore result
System.out.printf("%2d%11d\n",i,fib1calls.value);
}

d. Extend the table from part (b) up to N=10.

N calls to fib(1) while computing fib(N)
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55

e. Given this table, how many calls to fib(1) are required, in general, when computing fib(n) recursively? (Note: Given that Fibonacci numbers grow exponentially fast, this should help you understand why the recursive version of fib slows down so much around n=40.)

When computing fib(n) recursively, there are fib(n-1) calls to fib(1)! Notice this is not fib(n), according to our definition of fib(n), since fib1calls(0)=0 and fib(0) = 1 by our definition (which is not entirely standard).

In any case, since fib(40) > 100 million, that’s a whole lot of recursive calls to compute fib(40), especially when you consider that the iterative version performs 40 simple arithmetic calculations to compute the same value!

5. Memoization (a kind of dynamic programming) is a technique which uses caching in order to combine the benefits of the clarity of recursive solutions with the speed of iterative solutions. Write a program, MemoizedFib.java (note that there is no “r” in Memoized), that uses memoization to dramatically speed up our recursive fibonacci method. The basic idea is to start with the recursive solution, and to store the results of calls to fib(i), so that repeated calls just use the stored values rather than recursively recomputing them. To do this, create an array of int’s, fibValues. For this problem, you can fix the maximum value of N to 99, and so you can set the size of fibValues to 100. You should also have a second array, isComputed, containing boolean values such that isComputed[n] is true if and only if fibValues[n] holds the value of fib(n) (hence, initially isComputed[n] should be false for all values of n, which conveniently is the default when you create an array of booleans). Now, on a call to fib(n), first check if isComputed[n] is true. If so, just return fibValues[n]. Otherwise, compute fib(n) recursively (still using memoization in your recursive calls!), and then set fibValues[n] to the result and isComputed[n] to true before returning the result. Write some test code that verifies that your memoized fib computes the same values as your recursive fib. Notice, though, that the runtimes of memoized fib are basically the same as iterative fib.
Here is the relevant code:
private static int[] fibValues = new int[100];
private static boolean[] isComputed = new boolean[100];
public static int memoizedFib(int n) {
if (isComputed[n]) return fibValues[n];
int result;
if (n < 2) result= 1;
else result = memoizedFib(n-1) + memoizedFib(n-2);
fibValues[n] = result;
isComputed[n] = true;
return result;
}
public static void main(String[] args) {
// This prints the table lickety-split!
for (int i=0;i<40; i++)
System.out.printf("%d%10d\n",i,memoizedFib(i));
// This is silent, so the memoized method works!
for (int i=0;i<40; i++)
if (fib(i) != memoizedFib(i))
System.out.printf("memoizedFib(%d) != fib(%d)\n",i,
}

6. Consider the following method:
public static int foo(int x, int y) {

if ((x < 1) || (y < 1)) return 0;

else return foo(x-1,y-1)+x+y-1;

}

a. Trace a call to foo(8,3)
foo(8,3)
foo(7,2)
foo(6,1)
foo(5,0)
--> 0
--> 6
--> 14
--> 24

While you should generate the trace by hand, you should also be able to instrument foo() so that it does this for you, as such:
public static int foo(int x, int y, int depth) {
for (int i=0; i<3*depth; i++) System.out.print(" ");
System.out.printf("foo(%d,%d)\n",x,y);
int result;

if ((x < 1) || (y < 1)) result = 0;
else result = foo(x-1,y-1,depth+1)+x+y-1;

for (int i=0; i<3*depth; i++) System.out.print(" ");
System.out.printf("--> %d\n",result);
return result;
}
public static void main(String[] args) { foo(8,3,0); }

b. Trace a call to foo(8,4)
foo(8,4)
foo(7,3)
foo(6,2)
foo(5,1)
foo(4,0)
--> 0
--> 5
--> 12
--> 21
--> 32

c. In just a few words of English, assuming its arguments are both non-negative, what does this method compute? (Hint: it is a common arithmetic expression).
For non-negative x and y, foo(x,y) = x*y. It computes the product.

d. Explain why your answer to part (c) is correct.

There are multiple ways to do this. For full credit, though, you cannot just “handwave”, but must have a mathematically sound explanation. Of the various approaches, here is my preference, as it explains the logic of the recursive case clearly:

First, we multiply (x – 1)(y – 1):
(x – 1)(y – 1) = xy – x – y + 1

Next, we solve this expression for xy:
xy = (x – 1)(y – 1) + x + y – 1

Notice that this is exactly the logic of the recursive case in the code above! Not a coincidence at all!!

Since our base case does compute the product xy when (x == 0) or (y == 0), and since our recursive case computes the product xy assuming f(x-1,y-1) computes (x-1)(y-1), we conclude f(x,y)=xy for all cases.

Now, for full rigor, we’d need to do a bona fide mathematical induction proof at this point (which would be very close to the above explanation, but with a little more rigor), but we’ll settle on this explanation.