Exam 2011, Questions and answers PDF

Preview

Summary

Download Exam 2011, Questions and answers PDF

Description

CSSE2002 / CSSE7023: Programming in the Large / Advanced Software Engineering – Final Examination, Semester Two, 2011 Question 1 [12 marks] For each of the Java programs below, indicate what is printed in the output window when the program is run. Question 1(a) [4 marks] public static void main(String[] args) { int int[] x = {7,2,5}; int y = 20; for (int i=0; i= 0 && t >= 0 * @ensure all users are in balances with value zero * && this.fifties == f && this.twenties == t * @param users a list of the valid user names * @param f the initial number of 50 dollar notes * @param t the initial number of 20 dollar notes */ public CashMachine(ArrayList users, int f, int t) { this this.fifties = f; this this.twenties = t; balances = new HashMap(); for (String u : users) { balances.put(u,0); } } /** * Deposit 20 and 50 dollar notes into the user's account * @require user != null && user.length() > 0 * && f >= 0 && t >= 0 * && (f > 0 || t > 0) * @ensure balances.get(user) == * \old(balances.get(user) + 50*f + 20*t * && this.fifties = \old(this.fifties) + f * && this.twenties = \old(this.twenties) + t * @param user the user whose account to credit * @param f the number of 50 dollar notes * @param t the number of 20 dollar notes * @throws CashMachineException if the user or amount * is invalid or does not hold an account */

Page 3 of 12

CSSE2002 / CSSE7023: Programming in the Large / Advanced Software Engineering – Final Examination, Semester Two, 2011 public void deposit(String user, int f, int t) throws CashMachineException { if (user == null || user.length() == 0) throw new CashMachineException(); if (!balances.containsKey(user)) throw new CashMachineException(); if (f < 0 || t < 0 || f + t == 0) throw new CashMachineException(); this this.fifties += f; this this.twenties += t; int newBalance = balances.get(user) + 50*f + 20*t; balances.put(user, newBalance); } /** * Withdraw an amount from the specified user's balance * @param user the user whose account to debit * @param amount the amount to withdraw * @throws CashMachineException if the amount is not valid * or not possible, or if the user is invalid/unrecognised */ public void withdraw(String user, int amount) throws CashMachineException { if (user == null || user.length() == 0) throw new CashMachineException(); if (!balances.containsKey(user)) throw new CashMachineException(); if (amount < 1 || balances.get(user) < amount) throw new CashMachineException(); int t = 0; int f = amount / 50; int leftover = amount - (f*50); if (leftover % 20 == 0) t = leftover / 20; else { f--; leftover = amount - (f * 50); if (leftover % 20 == 0) t = leftover / 20; else throw new CashMachineException(); } if (f > this .fifties || t > this this.twenties) throw new CashMachineException(); this this.fifties -= f; this this.twenties -= t; int newBalance = balances.get(user) - amount; balances.put(user, newBalance); } }

Page 4 of 12

CSSE2002 / CSSE7023: Programming in the Large / Advanced Software Engineering – Final Examination, Semester Two, 2011

Question 2(a) [6 marks] Provide a precondition and postcondition for the withdraw() method, in the form of @require and @ensure clauses which could be added to the javadoc, using semi-formal English or more formal syntax (in the style of the specification for deposit()). The precondition should guard against all exceptions thrown in the method, and the postcondition should ensure the 3 state variables are updated appropriately. Note: The machine may issue any number of 50 and 20 bills that satisfy the amount, e.g. 2x$50 and 5x$20 are both legal withdrawals for $100.

Solution: @require user != null && user.length > 0 user in balances.keySet() && amount > 0 && balances.get(user) >= amount && amount == 50x + 20y for integers x,y such that x >= 0 && y >= 0 && x >= \old(fifties) && y >= \old(fifties) @ensure balances.get(user) = \old(balances.get(user)) - amount \old(fifties) * 50 + \old(twenties) * 20 == fifties*50 + twenties*20 + amount

Question 2(b) [6 marks] Write a program that performs three tests on the deposit() method: one for when the user is not known, one for when the t and f parameters are negative, and one for when the deposit is successful.

Example solution: public static void main(String[] args) { ArrayList users = new ArrayList(); users.add("Jack"); CashMachine m = new CashMachine(users, 2, 2); try { m.deposit("Mike", 1, 1); } catch (CashMachineException n) { System.err.println("Expected exception"); } try { m.deposit("Jack", -1, -1); } catch (CashMachineException e1) { System.err.println("Expected exception"); } try {

Page 5 of 12

CSSE2002 / CSSE7023: Programming in the Large / Advanced Software Engineering – Final Examination, Semester Two, 2011 m.deposit("Jack", 1, 1); } catch (CashMachineException e1) { System.err.println("Unexpected exception"); } }

Page 6 of 12

CSSE2002 / CSSE7023: Programming in the Large / Advanced Software Engineering – Final Examination, Semester Two, 2011 Question 3 [12 marks] Consider the following requirements for a jigsaw puzzle game. When the program starts, an image file is loaded and cut into pieces. The user is then presented with a window with a board, on which the pieces are placed in random locations. The user can drag a piece next to another piece; if they are adjacent pieces, they will snap together and form a composite piece. When the user has assembled all pieces, a dialog is presented announcing that they have completed the puzzle.

Question 3(a) [4 marks] Identify four domain/analysis classes in this problem, and give a brief one-sentence description of each. Describe how they relate to one another. Solution sketch: Some examples of possible classes: - Puzzle: The puzzle that the user has to solve - Piece: a piece of the puzzle - CompositePiece: a group of joined pieces - Game: the game that the user is playing - Board: the board with the user’s current attempt at the puzzle - Window: the window that the user sees - WinDialog: the dialog the user sees when they win

Question 3(b) [8 marks] Identify four design classes in this problem. These might correspond to the domain/analysis classes, or they might not. For each of these classes, provide • a brief one-sentence description of the purpose of the design class within the design, • two variable/fields or methods the class would have (with types – the type can be either simple type or references to other design classes), and a brief description of what the field/method is for.

Solution sketch: Example of design classes that make sense: - PuzzleImage: int sizex, sizey, List cut() - Puzzle: int sizex, sizey, numPieces, pieceList: List, Boolean isComplete(), void complete() - PuzzleBoard: display(), initialize(), cutPuzzle(), image, pieces - WinDialog: display(), close(), numPieces - GameManager: start(), cutPuzzle(), isComplete(), newGame()

Page 7 of 12

CSSE2002 / CSSE7023: Programming in the Large / Advanced Software Engineering – Final Examination, Semester Two, 2011 Question 4 [12 marks] Question 4(a) [6 marks] The following algorithm calculates x^y using only multiplication and division. /** * Calculate a^n using only multiplication and division * @require a > 0 && n >= 0 * @ensure \result = a ^ n * @param a the base * @param n the exponent * @return r such that r = a^n */ public static int power(int base, int exp) { int x = base; int y = exp; int power = 1; while (y > 0) { /** * loop inv: power*x^y == base^exp */ if (y % 2 != 0) power = power*x; x = x*x; y = y/2; } return power; }

Describe how the provided loop invariant for the while loop, can be used to prove partial correctness and total correctness for power(). Solution sketch: Show it is true in the first iteration Show it is true in subsequent iterations Show the postcondition is true Show it converges

Page 8 of 12

CSSE2002 / CSSE7023: Programming in the Large / Advanced Software Engineering – Final Examination, Semester Two, 2011 Question 4(b) [6 marks] The following code is an implementation for the Euclidean method for calculating the greatest common denominator of two integers x and y. public static int gcd(int int x, int y) { int a = x; int b = y; while (b != 0) { if (a > b) a = a - b; else b = b - a; } return a; }

Provide an implementation of this method based on recursion, rather than iteration (you are not required to provide javadoc). Solution: public static int rgcd(int int a, int b) { if (b == 0) return a; else if (a > b) return gcd(a-b,b); else return gcd(a,b-a); }

Page 9 of 12

CSSE2002 / CSSE7023: Programming in the Large / Advanced Software Engineering – Final Examination, Semester Two, 2011 Question 5 [12 marks] Consider the following three class definitions. public class Foo { /** @require no string can occur twice in ls * @ensure for x, y in ls, x.length < y.length * implies ls.indexOf(x) < ls.indexOf(y) */ public void method(List ls) { } }

public class Bar extends Foo { /** @require no two strings in s may have the same * first 3 characters * @ensure for x, y in ls, x.length < y.length * implies ls.indexOf(x) < ls.indexOf(y) */ public void method(List list) { } public void method(List list, int n) { } }

public class Toto extends Bar { /** @require no string can occur twice in ls * @ensure ls is sorted by length, strings of the * same length are in alphabetical order */ public void method(List ls) { } }

Page 10 of 12

CSSE2002 / CSSE7023: Programming in the Large / Advanced Software Engineering – Final Examination, Semester Two, 2011 For each of the next 3 questions, indicate whether the code fragment would compile successfully. If it does not compile, explain the reason. If it does compile, indicate whether the code would run successfully or if not, indicate what Exception would be thrown. Question 5(a) [2 marks] Foo f = new Foo(); Bar b = new Bar(); f = b;

Solution: compiles and runs fine.

Question 5(b) [2 marks] Bar b = new Bar(); Toto t = new Toto(); b = (Bar) new Foo(); b.method(new new ArrayList(), 2);

Solution: compiles fine, ClassCastException cannot convert Foo to Bar.

Question 5(c) [2 marks] Foo f = new Foo(); Bar b = new Toto(); f = b; f.method(new new ArrayList(), 0);

Solution: does not compile, method(list) it not applicable for the arguments method(list, int)

Question 5(d) [3 marks] Does Bar satisfy the substitution principle with respect to class Foo? Explain why/why not.

Solution: No. Postcondition is unchanged, and Precondition has been strengthened.

Page 11 of 12

CSSE2002 / CSSE7023: Programming in the Large / Advanced Software Engineering – Final Examination, Semester Two, 2011 Question 5(e) [3 marks] Does Toto satisfy the substitution principle with respect to class Bar? Explain why/why not.

Solution: Yes. Precondition has been weakened, postcondition has been strengthened.

Page 12 of 12...