<![CDATA[
Problem #1
solution
1. Method Call Output Produced
------------------------------------------------
mystery(4, 1); 4
mystery(4, 2); 8, 4, 8
mystery(8, 2); 16, 8, 16
mystery(4, 3); 12, 8, 4, 8, 12
mystery(3, 4); 12, 9, 6, 3, 6, 9, 12
3 points for each row.
First row is all-or-nothing. For others, they lose 1 point for each incorrect
number or missing number or comma error, although they can't go below 0 for any
single row and the comma errors should be capped at -2 for the entire problem.
-0 for quotes around output
Problem #2
solutions
public static boolean sameDashes(String s1, String s2) {
if (s1.length() != s2.length())
throw new IllegalArgumentException();
if (s1.length() != 0) {
if (s1.charAt(0) == '-' && s2.charAt(0) != '-') {
return false;
}
if (s2.charAt(0) == '-' && s1.charAt(0) != '-') {
return false;
}
return sameDashes(s1.substring(1), s2.substring(1));
}
return true;
}
public static boolean sameDashes(String s1, String s2) {
if (s1.length() != s2.length()) {
throw new IllegalArgumentException();
} else if (s1.length() == 0) {
return true;
} else if (s1.charAt(0) == '-' || s2.charAt(0) == '-') {
return s1.charAt(0) == s2.charAt(0) &&
sameDashes(s1.substring(1), s2.substring(1));
} else {
return sameDashes(s1.substring(1), s2.substring(1));
}
}
1 header (okay if it's static)
2 exception
1 attempt
1 correct
7 generous (don't take off for syntax for these)
1 testing string length of 0 or 1 or testing for equality with empty string
1 testing whether a char from either string is a dash
1 testing for a dash/non-dash combination in one direction
2 testing for a dash/non-dash combination in the other direction
1 attempt to recurse with shorter strings by calling substring on each
1 recursive call that correctly shortens each string by 1 char (if they
have an obob on their call to substring, take off this point and then
pretend it works in grading the "actually works" points below)
5 actually works (see note below about syntax)
1 returns true for empty strings without throwing an exception
2 works correctly when either string begins with a dash (correct test,
returns false if they don't match, correct recursive for rest of string)
2 makes correct recursive call when neither string begins with a dash
(requires some attempt to test for dashes with a separate case for this)
syntax deductions (categorical, first mistake is free if there weren't
other syntax problems in their code)
-1 for confusing equals and == on string/char
-1 for confusing length/length()/size/size()
-1 for failing to say "return" with a recursive call
note: all loop or extra data structure solutions go to question leader
the criteria assume students are looking at the first character of
strings, but you should adjust appropriately for other approaches that
work (e.g., they look at the last character or they introduce a private
method with an index parameter).
Problem #3
before after code
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[2]->[3] | p->[1]->[3] | q = p.next;
| | p.next = p.next.next;
| | q.next = null;
q | q->[2] |
| |
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[3] | p->[1]->[2]->[3] | q.next = p.next;
| | p.next = q;
| | q = null;
q->[2] | q |
| |
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[2] | p->[2]->[4] | p.next.next = q.next;
| | q.next = p;
| | p = p.next;
q->[3]->[4] | q->[3]->[1] | q.next.next = null;
| |
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[2]->[3] | p->[3]->[1]->[5] | p.next.next.next = p;
| | ListNode temp = q.next;
| | q.next = p.next;
q->[4]->[5] | q->[4]->[2] | p.next = temp;
| | p = q.next.next;
| | q.next.next = null;
| |
-----------------------+-----------------------+-------------------------------
3 problem 1
1 attempt: change 2 of (q, 2 ~.next)
2 correct
3 problem 2
1 attempt: change 2 of (q, 2 ~.next)
2 correct
4 problem 3
1 attempt: change 2 of (p, 3 ~.next)
1 better attempt: change all 4 of (p, 3 ~.next)
2 correct
5 problem 4
1 attempt: change 2 of (p, 4 ~.next)
1 better attempt: change 4 of (p, 4 ~.next)
3 correct
Notes
correctness is generally atomic except:
-1 per "setting to null" error if otherwise correct
-1 per exception thrown if otherwise correct
-1 if adding or subtracting a single ".next" somewhere makes it work
can lose up to 2 syntax points if they get correctness points, examples:
-1 not declaring temp variable to be of type ListNode
-1 saying p.next() instead of p.next
-1 per occurrence (max of 2) for "p.data" instead of "p" or equivalent
Problem #4
Statement Output
------------------------------------------------------------
var1.method1(); Wall 1
var2.method1(); Dragon 1/Raven 1
var3.method1(); Raven 1
var4.method1(); compiler error
var5.method1(); Wall 1
var6.method1(); compiler error
var1.method2(); Raven 2/Wall 1
var2.method2(); Raven 2/Dragon 1/Raven 1
var3.method2(); Raven 2/Raven 1
var4.method2(); compiler error
var5.method2(); Raven 2/Wall 1
var6.method2(); compiler error
((Dragon)var1).method3(); compiler error
((Hand)var6).method3(); Hand 3
((Wall)var4).method1(); runtime error
((Raven)var6).method2(); Raven 2/Raven 1
((Raven)var4).method1(); Dragon 1/Raven 1
((Wall)var6).method3(); runtime error
((Wall)var3).method3(); runtime error
((Wall)var5).method3(); Wall 3
1 pt each
-1 if no slashes anywhere
-0 if they put quotes around answers
Problem #5
solution
public boolean isSorted(Stack<Integer> s) {
if (s.size() <= 1)
return true;
else {
Queue<Integer> q = new LinkedList<Integer>();
int prev = s.pop();
q.add(prev);
boolean ok = true;
while (!s.isEmpty()) {
int next = s.pop();
if (prev < next)
ok = false;
q.add(next);
prev = next;
}
while (!q.isEmpty())
s.push(q.remove());
while (!s.isEmpty())
q.add(s.pop());
while (!q.isEmpty())
s.push(q.remove());
return ok;
}
}
2 header (-1 per error, okay if it's static)
2 constructs temporary queue using generics correctly (-1 per error)
2 special test for size < 2 or equivalent
4 first S -> Q, Q -> S
2 attempt
2 correct
4 second S -> Q, Q -> S
2 attempt
2 correct
4 compare adjacent values correctly
2 correct test (-1 if just equals case is wrong)
2 all pairs tested
5 restores stack in all cases (normally lose this if they return early)
2 attempt (flag or code to restore before returning)
3 correct
2 always returns appropriate values (flag or true/false)
notes:
-5 for using peek, then grade normally
Give to question leader all solutions that involve:
foreach loop, iterator, or other illegal stack/queue operations
constructing a temporary structure other than a queue (e.g., a 2nd stack)
nonworking solution that gets 25 points
Problem #6
solutions
public void collapse() {
for (int i = 0; i < size / 2; i++) {
elementData[i] = elementData[2 * i] + elementData[2 * i + 1];
}
if (size % 2 == 0) {
size = size / 2;
} else {
elementData[size / 2] = elementData[size - 1];
size = size / 2 + 1;
}
}
public void collapse() {
int j = 0;
for (int i = 0; i < size / 2; i++) {
elementData[i] = elementData[j] + elementData[j + 1];
j += 2;
}
if (size % 2 != 0) {
elementData[size / 2] = elementData[size - 1];
}
size = (size + 1) / 2;
}
1 header (non-void okay if there is a return that is consistent)
5 collapsing loop (even case)
1 attempt (loop that adds consecutive values)
2 loops size/2 times (-1 if obob)
2 copies sums into correct positions
1 attempt (i*2 and i*2+1 or i and j with i++ and j+=2 or equivalent)
1 correct
2 copies final value in odd case
1 attempt
1 correct (requires a test for this case)
2 resets size
1 attempt (some version of size / 2 or size-- in a loop)
1 correct for both odd & even length
Notes: -3 if they use an extra structure (array, ArrayList, etc)
-1 if they use elementData.length instead of size
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011