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

Homework #3 (part 1)

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

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!

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

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.

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.

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).

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.

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

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

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.)

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.

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)

b. Trace a call to foo(8,4)

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).

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