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