CS307 Fall 2008, Midterm 2 suggested solutions and grading criteria Grading acronyms OBOE - Off by one error. Calculation is off by one. AIOBE - Array Index out of Bounds Exception will occur NPE - Null Pointer Exception will occurs ABA - Answer by Accident GCE - Gross Conceptual Error. Did not answer the question asked or showed fundamental misunderstanding NAP - No answer provided. No answer given on test ECF - Error carried forward. BOD - Benefit of the Doubt. Not certain code works, but, can't prove otherwise Gacky or Gack - Code very hard to understand even though it works or solution is not elegant. (Generally no points off for this.) 1. 1. Answer as written or -1. Ignore differences in capitalization. On Big O, it is okay if missing O(). On Big O if extra term or coefficient (other than base on log) -2. A. O(N) B. O(N^2) C. O(logN) // base 3 okay D. O(NlogN) // base 2 okay E. O(N) F. O(1) G. O(N^3) // recall get from LinkedList is O(N) H. 4N^2 + 4N + 5 // + or - one on all coefficients. So for example 3N^2 + 5N + 4 is okay. I. 10,000 // all of them! J. 16 seconds K..021 seconds // as long as no logs left, other expressions okay if equal to .021 L. insertion sort // clearly O(N), insertion sort was the only sort we looked at in class that was naturally O(N) on pre sorted data. M. 10 N. deeppppp O. BABB // differences in capitalization okay 2. Meant to be an easy question because it was only necessary to traverse the linked list. Majority of points were for correctly traversing the linked list. The majority of students did well on the question although some did make it a lot harder than it needed to be. For example, the suggested solution handles an empty list without a special case, where as a lot of students thought this would be a special case. Suggested Solution: public int numPresent(Object value){ int count = 0; Node temp = head; while(temp != null){ if( value.equals( temp.getData() ) ) count++; temp = temp.getNext(); } return count; } Grading Criteria: correctly create temp Node: 1 point traverse list: attempt 3 points, correct 8 points. (in context of a loop) test equality of objects: attempt 2 points, correct 2 points (in context of a loop) count num objects equal: 3 points must be correct return answer: 1 point Common problems: destroying the list. Instead of using a temp node several students used the head node to traverse the list, thus destroying the list. Destroying a data structure in anything but the clear / makeup methods is not okay. -6 Lots of off by on errors. Missing the data in the first node or last node because of check. Using == instead of .equals to compare data. Confusion between Node objects and Node variables such as checking for an empty list via head.getData() == null (incorrect) instead of head == null (correct). Also things such as temp.getData() != null to see if walked off list which is again, not correct. relying on size or tail which did not exist in this linked list class There were a couple of correct recursive solutions. (Future lisp programmers no doubt.) 3. Same problem as the section quiz a couple of weeks ago. The TAs graded this question. It was acceptable to use a new array instead of shifting in the same array. Suggested Solution public void removeAll(Object obj){ int posToShiftTo = 0; int numFound = 0; for(int i = 0; i < size; i++){ if( container[i].equals(obj) ){ numFound++; } else { container[posToShiftTo] = container[i]; posToShiftTo++; } } for(int i = 0; i < numFound; i++) container[size - i] = null; size -= numFound; } Alternate using a new array. public void removeAll(Object obj){ Object[] newCon = new Object[container.length]; int newSize == 0; for(int i = 0; i < size; i++){ if( !container[i].equals(obj) ){ newCon[newSize] = container[i]; newSize++; } } container = newCon; // let gc do its job seize = newSize; } Grading Criteria: loop through valid elements of container (must be size, not container.length) attempt: 3 points, correct 3 points test elements in container to see if they are equal to obj. (Must be in context of a loop): attempt 3 points, correct 3 points either shift elements down in current container or add to new container: attempt 3, correct 3 points update size correctly: 2 points Common errors where all correctness points not lost off by one error: -1 didn't null out old elements if not using a new container: -2 == instead of .equals on objects -2 4. A question about using iterators and existing data structures. There was a very simple answer and another answer that improved on efficiency, but was not required. Most students did reasonably well. Suggested Solution: (Simple version) public static int numGreater(TreeSet set, Integer value){ Iterator it = set.iterator(); int numGreater= 0; while(it.hasNext() ) { if( it.next().compareTo(value) > 0) numGreater++; } return numGreater; } More efficient solution: public static int numGreater(TreeSet set, Integer value){ Iterator it = set.iterator(); int numLessOrEqual = 0; while(it.hasNext() && value.compareTo(it.next()) >= 0){ numLessOrEqual++; } return set.size() - numLessOrEqual; } Grading Criteria create iterator correctly: 3 points use iterator: attempt: 2 points, correct 3 points test values greater than (or less, equal) than depending on logic: attempt 2 points, correct 2 points determine number greater: 2 points return: 1 point Common problems: Not getting iterator correctly. Saw a lot of Iterator it = new Iterator(); // wrong or Iterator it = new Iterator(set); // wrong Some people assumed compare to always returns -1 or 1. This is not the case. Problems on logic with compareTo 5. Ouch. I suppose I deserve the headache I got from grading for giving a question unlike anything you had seen before. There were only a handful of solutions like the one I came up with. To guarantee the best answer you had to generate all possible combinations of items that would fit and pick the best one. The major approaches were: A. Loop through items and recurse on each item. this could work, but made more calls than were necessary. See the second suggested solution. B. Greedy algorithms. SOme students simply picked the highest value item first and then the next highest that would fit and so forth. This does not always work. Some students picked the item with the highest density of value (dollars per pound) that would fit and then the next that would fit and so forth. These are called "greedy algorithms" and while they are a decent heuristic they do not guarantee the best answer in this case. To see why consider if there were only 3 items: one 9 pound item worth 9 dollars one 8 pound item worth 7 dollars one 7 pound item worth 6 dollars Each greedy algorithm would pick the 9 pound 9 dollar item first (Highest value and highest density) and miss the best solution of taking the 8 pound and 7 pound item C. Try to generate all the combinations recursively or iteratively. And then pick the best. I didn't see any along these lines that worked. D. The suggested solution to generate combinations and track the best as you go. Suggested Solutions: public static int getMaxValue(ArrayList things, int capacity){ if(things.size() == 0 || capacity <= 0) return 0; else{ Item temp = things.remove(things.size() - 1); // try without this item in the bag int result = getMaxValue(things, capacity); if( temp.getWeight() <= capacity ){ // try with this item in the bag int with = temp.getValue() + getMaxValue(things, capacity - temp.getWeight()); result = Math.max(result, with); } things.add(temp); // put it back for later combinations return result; } } // this works, but does a lot of repeat work public static int getMaxValue(ArrayList things, int capacity){ int maxSoFar = 0; int value = 0; for(int i = 0; i < things.size(); i++){ // check if it fits. Lots of students forgot this if( things.get(i).getWeight() <= capacity){ Item tempItem = things.remove(i); value = getMaxValue(things, capacity - tempItem.getWeight()) + tempItem.getValue(); if( value > maxSoFar ) maxSoFar = value; things.add(i, tempItem); // must put back to allow later combos } } return maxSoFar; } No set criteria because answers were so wildly different.