CS307 fall 2009 Midterm 2 Solution and Grading Criteria. Grading acronyms: ABA - Answer by Accident, right answer, wrong approach AIOBE - Array Index out of Bounds Exception may occur BOD - Benefit of the Doubt. Not certain code works, but can't prove otherwise ECF - Error carried forward. Gacky or Gack - Code very hard to understand even though it works or solution is not elegant. (Generally no points off for this.) GCE - Gross Conceptual Error. Did not answer the question asked or showed fundamental misunderstanding LE - Logic error in code. Solution incorrect due to logic error. NAP - No answer provided. No answer given on test NN - Not necessary. Code is unneeded. Generally no points off NPE - Null Pointer Exception may occur OBOE - Off by one error. Calculation is off by one. 1. Answer as shown or -2 unless question allows partial credit. No points off for differences in spacing and capitalization. On Big O no coefficients. O(N/2) is wrong if answer is O(N). On Big Just function is okay. If Answer is O(N) just N is correct as well. On best case big error to assume N = 1. Must still assume N can be large otherwise best case is always O(1) and we wouldn't even consider best cases. A. 11 B. kcats C. 22 D. 247 E. O(N) F. O(N) G. 0(N^2) H. O(N) I. O(N^2) J. O(N) K. O(N^2) (worth 1 point) This occurs when the min or max value of the data is always picked as the pivot. (Or words to that effect. 1 point) L. O(NlogN) (base 2 okay) M. 24 seconds N. everyone gets credit. (Correct answer is (100,000^2 * 0.6) ^ (1/2) O. 5137 2. This was not meant to be a very difficult question. One had to use iterators or the for each loop. Helper methods were allowed. I thought this was an easy question, but there were many problems with using the iterators correctly and getting the algorithm correct. Suggested Solution 1 public boolean areDisjoint(ISet other){ boolean disjoint = true; Iterator thisIt = this.iterator(); while(disjoint && thisIt.hasNext()){ E val = thisIt.next(); Iterator otherIt = other.iterator(); while(disjoint && otherIt.hasNext()){ disjoint = !val.equals(otherIt.next()); } } return disjoint; } Suggested Solution 2: public boolean areDisjoint(ISet other){ for(E val : this) for(E otherVal : other) if(val.equals(otherVal)) return false; return true; } Grading Criteria: 17 points: (Solution can be "inverted" where this is other and other is this. obtain iterator for this set: 3 points (for each loop okay) use iterator correctly to access an element at a time from this set, 3 points (for each loop okay) check each element in this set to see if present in other. - obtain iterator for other repeatedly 3 points (for each loop okay) - use iterator correctly to access an element at a time from other set, 3 points (for each loop okay) - check equality of object with equals (3 points) stop checking as soon as known not disjoint 1 point return correct answer 1 point No generic syntax is okay. Object instead of E okay Iteartor it = new Iterator(); -5 == instead of .equals -3 using methods from AbstractSet if not written by student on exam: -6 Use of temporary array (or not O(1) space) -6 3. This was a fairly simple array based list question. A bit of complexity because there were two lists involved, the original and the result. Size of resulting GenericList container had to be set to be large enough to hold sub list. This could be done directly or by adding a constructor or by writing a resize method. Again, I thought this was easy, but the graders saw lots of problems. Suggested Solution: public GenericList getReversedSubList(int start, int stop){ assert 0 <= start && start <= stop && stop <= size(); GenericList result = new GenericList(); result.container = new Object[stop - start + 10]; int indexInResult = 0; for(int i = stop - 1; i >= start; i--){ result.container[indexInResult] = this.container[i]; indexInResult++; } result.listSize = stop - start; return result; } Grading Criteria: 18 points Create resulting list: 2 points Ensure enough capacity in resulting list: 3 points (multiple ways of doing this. New constructor, resize, method or as shown in solution. Extra capacity in resulting GenericList internal array NOT necessary.) loop through indices of sub list: - attempt: 2 points - correctly: 3 points place elements in result in correct order and positions. - attempt 2 points - correct 3 points set listSize variable in result to correct value: 2 points return result: 1 point Potential problems: result[index] is -4 using methods from GenericList if not written by student on exam: -6 4 I really liked this question. It required an understand of pointers. (Lots of questions during the exam indicating some students did not know the difference between the variable first and the node that first is referring to.) Easiest solution required use of a trailer node. No methods from the linked list class would really help. (The iterator returns the data, not the nodes.) Some very confusing attempts. Suggested Solution: private boolean prevsSetCorrectly() { boolean correct = true; DoubleListNode leader = first; DoubleListNode trailer = null; while(leader != null && correct){ correct = leader.getPrev() == trailer; trailer = leader; // or trailer = trailer.getNext() leader = leader.getNext(); } return correct; } Alternate solution: private boolean prevsSetCorrectly() { boolean goodLinks = true; if(first != null) goodLinks = first.getPrev() != null; Node temp = front; while(temp != last && goodLinks){ goodLinks = temp.getNext().getPrev() == temp; temp = temp.getNext(); } return goodLinks } On the alternate solution a lot of students forgot to check the first prev link was null. Grading criteria: 18 points Temp node variable for leading initialized to first: 2 points Temp node variable for trailing: 1 point loop while list correct and still nodes to check: - attempt 2 points - correct 2 points check that lead node's previous pointer refers to correct value / node: 4 points move lead node: 3 points move trailer node: 3 points return 1 point 5. A good example of a brute force recursive backtracking. Some big problems were making the recursive call without doing the move which will cause a stack overflow error because the same set of moves comes up. Another problem was not getting the moves for the new board. After a move was made if it wasn't successful the moved needed to be undone. And finally some solutions returned the first attempt, true or false, instead of going forward again. Suggested Solution public static boolean canBeSolved(char[][] board){ if(numMarblesOnBoard(board) == 1) return true; ArrayList moves = getLegalMoves(board); for(LegalMove move : moves){ // move marble and remove marble jumped over board[move.sourceRow()][move.sourceCol()] = 'o'; board[move.destRow()][move.destCol()] = 'm'; board[move.removedRow()][move.removeCol()] = 'o'; if(canBeSolved(board)) return true; // maybe while loop and boolean would be // better instead of return buried in loop // put them back to try other moves board[move.sourceRow()][move.sourceCol()] = 'm'; board[move.destRow()][move.destCol()] = 'o'; board[move.removedRow()][move.removeCol()] = 'm'; } // tried all possibilities, none of them worked return false; } Grading criteria: 17 points: get numMarbles: 1 point base case solved with 1 marble: 2 points get legal moves for new board: 1 point loop through the new moves: 2 points apply move: 3 points recursive call on changed board: 3 points (in loop) if solved return true: 2 points undo move if necessary: 2 points return false if no moves work: 1 point