CSE 321 Winter 2010
Homework #4

Due Friday, February 5h at the start of lecture (right before the
midterm).  Bring to class to turn in.  Justify/prove all your answers.

1 [10 points].   Consider the program fragment below:

x = y - x;
y = z - y;
z = z - x;
x = x + z;
z = y - z;
y = x - y;

Explain what it computes, then prove your claim formally.

2 [10 points]. How many lines does the function hello(n) print ?  Your answer
should be an expression in terms of n.

    public static void hello(int n) {
	for (int i = 0; i<n; i++)
	    for (int j = 0; j<i; j++)
		for (int k = 0; k<j; k++)
		    System.out.println("Hello");
    }


3 [30 points]. Consider the following program fragment:

    public static int c = 0, s = 0, t = 0;

    public static void f(int n) {
	if (n > 0) {
	    c++;
	    s += c;
	    f(n-1);
	    t += c;
	}
    }

    public static void main( String [ ] args )
    { int m = ...;  // doesn't modify c,s,t
	f(m);
       . . .
    }

   Write explicit formulas for the values of c, s, and t after calling
   the function f(n), in terms of m.


4 [50 points]. Consider the alphabet Sigma = {a,b}.  The following function
computes a string over Sigma.  Give the formula for the length for the
string f(n), as a function of n.

    public static String f(int n) {
	if (n==0) return "c";
	if (n==1) return "acb";
	if (n==2) return "aacbb";
	return f(n-2)+f(n-1)+f(n-2)+f(n-3)+f(n-2);
    }