CS307 Spring 2008 Midterm 1 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. 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. If quotes included, okay. A. 17 B. 2.0 C. 4 D. Runtime error OR exception OR NullPointerException OR program crashes E. 1 2 3 -3 5 7 -1 10 4 F. 2000 Size: 1000 G. Size: 750 Size: 750 H. Size: 75 (Note: The reference is not printed out. This results in a call to toString on the object cp is referring to.) I. Runtime error if assertions are on OR JUST Runtime error OR AssertionError OR program crashes J. UCSD, Size: 750 K. Syntax error or Compile error L. class: AAAAA M. UT, Size: 750 N. No O. Trade, TimeStamp, Comparable, Object (all 4 needed. No partial credit) 2. Comments: Any question that involves moving or shifting elements in an array leads to a variety of different solutions. I think the simplest approach was to find the min and then shift elements. It was necessary to maintain the relative order of all elements except the minimum. Common problems: - Trying to solve the problem with nested loops. These solutions tried to find the min and shift elements at the same time. This destroys the order of the other elements in the list. - using iValues.length instead of iSize or size(). The capacity of the internal storage container (the array) is not necessarily the size of the list. - failure to maintain relative order of elements Suggested Solution public void moveMinToFront(){ int posOfMin = getPosOfMin(); int temp = iValues[posOfMin]; for(int i = posOfMin; i > 0; i--) iValues[i] = iValues[i - 1]; iValues[0] = temp; } private int getPosOfMin(){ int posOfMin = 0; for(int i = 1; i < iSize; i++) if( iValues[i] < iValues[posOfMin]) posOfMin = i; return posOfMin; } Point breakdown find min attempt 4 points find min correct 4 points shift items attempt 4 points shift items correct 4 points min to front attempt 2 points min to front correct 2 points 3.Comments: Not intended to be a difficult problem because no elements had to be shifted. There was however a lot involved due to the abstractions involved. (arrays and Lists. Object variables and objects. two lists involved. The data type of iValues should have been Object[] bot iObject[].) Again, the internal storage containers could have extra capacity. Common problems - using == instead of .equals method - neglecting to consider elements of the list that are null. The example showed that nulls could be present. - checking that the data types were the same. This was unnecessary, but points were not deducted. The various equals methods will handle this. - trying to call an equals method on the arrays. - confusion between length of array and size of list. - only checking half this list. This can give an incorrect answer since there are 2 lists. For example only check half of [1, 2, 3, 4] and [5, 5, 2, 1]. - confusion between List object and array. other[i] is incorrect. Suggested Solution public boolean isReverse(List other){ boolean result = iSize == other.iSize; if( result ){ int i = 0; int j = iSize - 1; while(result && i < iSize){ if( iValues[i] == null || other.iValues[j] == null) result = iValues[i] == other.iValues[j]; else result = iValues[i].equals(other.iValues[j]); i++; j--; } } return result; } Point breakdown check sizes the same attempt 1 point check sizes the same correct 2 point traverse calling object's array attempt 1 points traverse calling object's array correct 2 points traverse parameter's array attempt 1 points traverse parameter's array correct 2 points compare correct items from each list attempt 1 points (positions correct) compare correct items from each list correct 3 points (must use .equals) handles null values correctly 3 points correctly check and track if elements are in reverse order 2 points return answer 2 points 4. I thought this was more difficult than question 3 but people generally did better on thesis question. Maybe because it wasn't so abstract. Common problems - hard coding for only 3 sizes (1, 2, 4). Just because the examples show 3 size does not mean those are the only sizes possible for the paint balls. - Failing to check inbounds for the initial hit and the splatter. Only the upper bounds had to be checked. Suggested Solution // certainly not the most efficient solution, but straightforward. public static boolean isCovered(int numRows, int numCols, PaintBall[] hits){ boolean[][] floor = new boolean[numRows][numCols]; int row, col, size; // go through all the paint balls for(int i = 0; i < hits.length; i++){ row = hits[i].getRow(); col = hits[i].getCol(); size = hits[i].getSize(); // initial hit when offsetFromHit = 0 and splatter for(int offsetFromHit = 0; offsetFromHit < size; offsetFromHit++){ if( row + offsetFromHit < floor.length) floor[row + offsetFromHit][col] = true; if( col + offsetFromHit < floor[0].length ) floor[row][col + offsetFromHit] = true; } } boolean all = true; row = 0; // check to see if whole floor covered while( all && row < floor.length ){ col = 0; while( all && col < floor[0].length ){ all = floor[row][col]; col++; } row++; } return all; } Points breakdown some way of tracking cells covered with paint 1 points loop through paint balls 1 point record initial square hit, correct 3 points attempt to splatter 2 points correctly splatter 3 points attempt check of all cells covered with paint 2 points correct check of all cells covered with paint 2 points return answer 1 point 5. Suggested Solution public class Course{ private int iNumCredits; private int iCourseNumber; private String iDepartment; // pre: credits > 0, 0 <= number <= 99999 public Course(int credits, int number, String dept){ assert credits > 0 && 0 <= number && number <= 99999 : "failed precondition"; iNumCredits = credits; iCourseNumber = number; iDepartment = dept; } // pre: newCredits> 0 public void changeCredits(int newCredits){ assert newCredits > 0 : "Failed precondition"; iNumCredits = newCredits; } public String toString(){ return "Course number: " + iCourseNumber + ", credits: " + iNumCredits + ", taught by " + iDepartment; } } Points breakdown: Class header 1 point (must be public) instance variables 4 points (must be private or lose 2 points) constructor preconditions 1 point constructor header 1 point constructor assert to check preconditions 1 point constructor assignment statements 1 point mutator for number of credits attempt 2 points mutator for number of credits correct 1 point mutator has precondition and assert 1 points toString header 1 point toString implementation 2 points. (full credit for reasonable attempts. Does not have to match solution format.)