Homework 4 Solutions
cs230 Fall 2000

1) power

    public static double power (double x, int n) {
	if (n == 0) return 1.0;
	return x * power (x, n-1);
    }

Number of recursions = n.

2) morePower

    public static double powerBetter (double x, int n) {
	if (n == 0) return 1.0;
	double half = powerBetter (x, n/2);
	if (n%2 == 0) {
	    return half*half;
	} else {
	    return half*half*x;
	}
    }

Number of recursions = log2 (n)

Note: make _one_ recursive call and save the result, otherwise
the number of recursions is 2 * log2 (n)

3) Ackerman's function

    public static int ack (int m, int n) {
	if (m == 0) return n+1;
	if (n == 0) return ack (m-1, 1);
	return ack (m-1, ack(m, n-1));
    }

Yes, I can prove this method terminates.

4) Something useful:

here is an iterative version of fibonacci.  You need two
extra variables (ult and penult) to keep track of the
previous two values.  Although this is efficient in time
(proportional to n) and space (constant), it is difficult
to prove correct.

    public static int fibonacci (int n) {
	if (n < 2) return 1;
	int ult = 1;
	int penult = 1;
	int next = 0;
	for (int i=1; i<n; i++) {
	    next = ult + penult;
	    penult = ult;
	    ult = next;
	}
	return next;
    }

an alternative is to accumulate the values in an array.
the space is now proporional to n, but it is easy to
show correctness

    public static int[] fibarray (int n) {
	int[] a = new int [n+1];
	a[0] = 1;
	a[1] = 1;
	for (int i=2; i<=n; i++) {
	    a[i] = a[i-1] + a[i-2];
	}
	return a;
    }

The problem with the recursive version of fibonacci is
that it takes space proportional to n and time proportional
to 2^n (exponential explosion).


5) Making change

    public static void main (String[] args) {
        int[] coinage = { 1, 5, 10, 25, 50 };
	System.out.println (countChange (100, coinage, 5));
    }

    public static int countChange (int amount, int[] coinage, int coins) {
	if (amount < 0) return 0;
	if (amount == 0) return 1;
	if (coins == 0) return 0;

	return countChange (amount, coinage, coins-1) +
	       countChange (amount- coinage [coins-1], coinage, coins);
    }

The base cases here are not obvious (for example, who
says there is one way to make change for zero cents?)

The recursive step should be clear, though.  The number
of solutions is the sum of two parts

1) all the solutions that don't use the largest coin

2) all the solutions that do use the largest coin

In the first case, we can reduce the problem to a smaller
number of coins.

In the second case, we can reduce the problem to a smaller
amount of change.

-----

There are 292 ways to make change for a dollar.

There are 4562 ways to make change for a pound
(using the coinage { 1, 2, 5, 10, 20, 50 }).

When I am King, a dollar will be worth 128 cents, and
the coinage will be { 1, 2, 4, 6, 16, 32, 64 }, and there
will be 35258 ways to make change!

Also, I will make Friday part of the weekend and give
every new baby a chocolate eclair.

Vote ME for King!