CS307 Spring 2009 Midterm 2 Solution and Grading Criteria. Grading acronyms ABA - Answer by Accident 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 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. As written or -2. No partial credit unless stated. On Big O, missing O() is okay. A. O(N^2) B. O(N) C. O(sqrtN) or O(N^1/2) D. O(N) E. 80 seconds F. 9 seconds G. 9 H. UTCSSSS I. 23 J. O(N) K. O(1) L. When the list is already sorted in the proper order. (or words to that effect) partial credit possible. M. 12 (11 - 13 okay) N. accessing all of the elements in order of position (or words to that effect) partial credit possible. O. KIGGOM EXTRA CREDIT: P. too long (1 point extra credit) 2. I thought this was the most difficult problem on the test due to having to deal with the abstraction of the FrequencyList and the pair objects, finding duplicates, knowing how to use the .equals method, and then shifting items forward in the list and updating size. There were MANY different approaches to the problem: one of the great things about programming. It was okay to create a new array as temporary storage. Common problems: - use con.length instead of the size instance variable this usually led to null pointer exceptions unless checked. - == instead of .equals - shifting when finding and removing a duplicate and not backing up the loop control variable - not using the methods from the Pair class correctly. Suggested Solution: public void consolidate(){ Pair[] temp = new Pair[con.length]; int numUnique = 0; for(int i = 0; i < size; i++){ boolean found = false; int indexInTemp = 0; while(!found && indexInTemp < numUnique){ found = con[i].getData().equals(temp[i].getData()); indexInTemp++; } if(!found){ temp[numUnique] = con[i]; numUnique++; } else{ // duplicate: Update freq of first occurrence. // Need to back up because we always // increment in while loop. indexInTemp--; temp[indexInTemp].increaseFreq(con[i].getFreq()); } } con = temp; size = numUnique; } // alternate solution that shifts right away public void consolidate(){ for(int i = 0; i < size; i++){ for(int j = i + 1; j < size; j++){ if(con[j].getData().equals(con[i].getData())){ con[i].increaseFreq(con[j].getFreq()); for(int k = j; k < size - 1; k++) con[k] = con[k + 1]; con[size - 1] = null; j--; size--; } } } } grading criteria: find duplicates: attempt: 2 pts, correct: 4 pts deal correctly with objects: 3 pts update freq correctly: 3 pts shift elements to front of list: attempt: 2 pts, correct 4 pts update size correctly: 2 pts. 3. Meant to be a relatively easy linked list problem. All that was required was to start at the head and get two temp Node pointers to refer to the Nodes specified by the parameters. Starting both movements from the head is okay. Suggested solution: public void swap(int pos1, int pos2){ assert pos1 >= 0 && pos1 < size && pos2 >= 0 && pos2 < size : "Failed precondition."; Node first = head; for(int i = 0; i < pos1; i++) first = first.getNext(); Node second = first; int linksBetween = pos2 - pos1; for(int i = 0; i < linksBetween; i++) second = second.getNext(); Object temp = first.getData(); first.setData(second.getData()); second.setData(temp); } grading criteria: Get reference to Node at position pos1 in linked structure of nodes: attempt 3 pts, correct: 4 pts Get reference to Node at position pos2 in linked structure of nodes: attempt 3 pts, correct: 4 pts swap data between nodes: attempt: 3 pts, correct: 3 pts. Other: - If list destroyed 8 points off (both of the correctness sections for moving through the list. (any head = new value besides first node or head.setNext() to any value other than second node) - If use methods from LinekdList that student doesn't write, 4 points off first time 4 more, second time. Again, these are the correctness points for moving through the list - using an array or ArrayList to solve the problem. (Not O(1) space) 8 points off, correctness. 4. Meant to be a question to show students could use an iterator as was required on the set assignment. The header on the test was wrong. The people who took the exam early were graded under a slightly different criteria. The regular and later exams were given the correct header. I gave the benefit of the doubt on most of the generic syntax. I also gave the benefit of the doubt to people who used the for each loop. It was not clear if the SortedSet class implemented Iterable or not, but it would be trivial to do so. Common problems: - missing one or both of the special cases. Some solutions did handle these under the general case. - not creating iterator correctly - not using iterator correctly. Lots of attempts that would have been infinite loops because the iterator was never advanced - lots of off by one errors. The kth element was 1 based, not 0 based as shown in the examples Suggested Solution with corrected header. public E getKth(SortedSet theSet, int k){ E result = null; if(! (k <= 0 || k > theSet.size()) ) { Iterator it = theSet.iterator(); for(int i = 0; i < k; i++){ result = it.next(); } } return result; } grading criteria: handle special cases: attempt: 1 pt, correct: 2 pts create iterator: attempt: 2 pts, correct: 2 pts iterate through SortedSet to obtain kth element: attempt: 3 pts, correct: 4 pts return value: 1 pt 5. The recursion problem. In fact this was a lot like the quiz from a couple weeks ago involving the number of ways to roll some number on a given number of 6 sides dice. There were some differences, but the problems were very similar. Shorten the name was fine. Common problems: - errors in base cases - looping through the rounds. The correct choice to consider at one step are win, lose, draw - not checking all possibilities - incorrectly summing the ways to achieve honorable mention - early return and not making all three recursive calls. Suggested solution: public static int waysToEarnHonrableMention(int rounds, int minPoints){ if(rounds == 0){ if(minPoints <= 0) return 1; else return 0; } else{ int ways = 0; for(int points = 1; points <= 5; points += 2){ ways += waysToEarnHonrableMention(rounds - 1, minPoints - points); } // okay to have hard code the 3 calls return ways; } } grading criteria: base cases: attempt 2 pts, all correct 2 pts make choices for current round (win, lose, draw): attempt: 2 pts, correct: 2 pts recursive call with adjusted values: attempt: 2 pts, correct: 2 pts sum results from all calls. (loop or add together calls): attempt: 1 pt, correct: 2 pts