1.(a) Suppose that - class C is a sub-class of another class P - variable x is an instance variable of class P (so x is either declared in P itself or is inherited from one of its superclasses) - variable x is declared as an instance variable in class C Then, the declaration of x in class C is said to shadow the variable declaration in the superclass. Similarly, a static variable in class C can shadow a static variable declared in a superclass of C. Suppose that - class C is a sub-class of another class P - method m with a certain type signature is an instance method declared either in class P or in one of superclasses of P - instance method m with the same type signature is declared in class C Then, the declaration of m in the child class C is said to override the method declaration in ites superclass. Similarly, a static method declared in C can override a static method with the same type signature declared in a superclass of C. (b) 7 (variable references are resolved using static binding) -7 (method names are resolved using dynamic binding) error error (interface does not have a declaration of variable i) -7 (dynamic method binding) error (interface does not have a declaration of method m2) -7 (variable references are resolved using static binding) -7 (dynamic method binding) -7 error (interface does not have a declaration of variable i) -7 (dynamic method binding) -7 (dynamic method binding) 2. (a) Base case: n = 2 Left hand side = 1/1*2 = 1/2 while Right hand side = 1/2. Cool. Inductive case: assume result for n = k >= 2, and show result for n = (k+1). For n = (k+1), left hand side = 1/1*2 + 1/2*3 + ... + 1/(k-1)*k + 1/k*(k+1) = (k-1)/k + 1/k*(k+1) by inductive assumption = k/(k+1) as required. (b) Base case: n = 1 Left hand side = 1/2 = 1/sqrt(4) Right hand side = 1/sqrt(3) So lhs <= rhs as required Inductive case: assume result is true for n = k >= 1 and show result for n = (k+1) For n = (k+1), left hand side = 1*3*5*...(2k-1)(2k+1)/2*4*6...2k*(2k+2) <= (2k+1)/(2k+2)*sqrt(2k+1) by inductive assumption = sqrt(2k+1)/(2k+2) right hand side = 1/sqrt(2k+3) To prove result, we must show that sqrt(2k+1)/(2k+2) <= 1/sqrt(2k+3) for all k >= 1 Squaring both sides, we see that we must show (2k+1)/(2k+2)*(2k+2) <= 1/(2k+3) which is the same as (2k+1)(2k+3) <= (2k+2)*(2k+2) Expanding this, we see that we need to show that 4k^2 + 8k + 3 <= 4k^2 + 8k + 4 which is obviously true. Therefore, the required result is proved. 3. ********************************************************************************* static boolean parse(String s) { CS211In f = new CS211In("exp.txt"); boolean gotIt = getExp(f); if (f.peekAtKind() == f.EOF) return gotIt; else return false; } static boolean getExp(CS211In f) { switch (f.peekAtKind()){ case f.INTEGER: {//E -> integer f.getInt(); return true; } case f.OPERATOR: {//E -> (E + E) if (f.getOp() != '(') //check for '(' return false; if(getExp(f)== false)//did we get an E? return false; if(! f.check('+')) //check for '+' return false; if (getExp(f)== false) //did we get another E? return false; if (! f.check(')')) //check for ')' return false; return true; } case f.WORD: {f.getWord(); if (f.check('(')){ // case E -> variable(E) if (getExp(f) == false) //got an E? return false; return f.check(')'); // got a ')' ? } else // case E -> variable return true; } default: return false; } } ********************************************************************************* Notes for grading: The only subtlety is in how the case of WORD is dealt with. Using check makes the code really simple. If the student's code is too complex, don't bother grading it - it is probably wrong. 4. (a) ********************************************************************************* static int stringToInt(String s){ // screen out "no string" cases: final int ILLEGAL=-1; if ( s == null || s.length()==0 ) return ILLEGAL; //some default value // build the int char-by-char: int num = 0; for (int i = 0; i < s.length(); i++) switch (s.charAt(i)) { case '0': num = num*10 + 0; break; case '1': num = num*10 + 1; break; case '2': num = num*10 + 2; break; case '3': num = num*10 + 3; break; case '4': num = num*10 + 4; break; case '5': num = num*10 + 5; break; case '6': num = num*10 + 6; break; case '7': num = num*10 + 7; break; case '8': num = num*10 + 8; break; case '9': num = num*10 + 9; break; default: return ILLEGAL; // quit early for non-decimal chars } // everything is OK: return the converted int: return num; } ********************************************************************************* Notes for grading: (i) This does not work: num*10 + s.charAt(i) (ii) Each case in switch statement must be a character. So this does not work: case 1: ... case 2: ... (b) - s1 = s2; This is an assignment. The reference stored in s2 is copied into s1. If s2 is null, both s1 and s2 are null after the assignment. Otherwise, s1 and s2 become aliases for the same String object. - (s1 == s2) This is a boolean expression. It returns true if s1 and s2 are aliases and false otherwise. - (s1.equals(s2)) This is a boolean expression. If s1 is null, this throws a null pointer exception. If s1 is not null, it returns true if s1 and s2 are strings with the same sequence of characters, and false otherwise.