<![CDATA[
Problem #1
solution
1. Method Call Output Produced
------------------------------------------------
mystery(7); 7
mystery(38); 3, 2
mystery(749); 7, 1, 0
mystery(-6842); 6, 2, 1, 2
mystery(954023); 9, 2, 1, 0, 2, 0
Problem #2
solution
public void parenthesize(String str, int n) {
if (n < 0) {
throw new IllegalArgumentException();
} else if (n == 0) {
System.out.print(str);
} else { // n > 0
System.out.print("(");
parenthesize(str, n - 1);
System.out.print(")");
}
}
1 header
2 exception
1 attempt
1 correct
4 n == 0 base case
1 attempt: some test on n that doesn't recurse
1 correct test (specifically check for n == 0)
2 works correctly for this case (printing string without parens)
notes: if n==1 is only base case, they lose "correct test" but can get
the other 3 points if the behavior is right
okay to have extra base cases if they are correct
8 recursive case
2 attempt: some kind of test that leads to a recursive call (usually else)
2 one recursive call on n-1
2 prints one left paren and one right paren for each call
2 correct order
general notes: using extra structure (like String) or using a loop goes to
question leader
-0 if they pass a new String for each recursive call "(" + s + ")"
-1 if they call println instead of print
-3 for calls on void method in print statement (only take off if this
raises their score)
Problem #3
solutions
public boolean hasOddEven() {
boolean odd = false;
boolean even = false;
ListNode current = front;
while (current != null && (!odd || !even)) {
if (current.data % 2 == 0) {
even = true;
} else {
odd = true;
}
current = current.next;
}
return odd && even;
}
public boolean hasOddEven() {
boolean odd = false;
boolean even = false;
ListNode current = front;
while (current != null) {
System.out.print(".");
if (current.data % 2 == 0) {
even = true;
} else {
odd = true;
}
if (odd && even) {
return true;
}
current = current.next;
}
return false;
}
1 header
3 loop to examine list elements
1 attempt ("current" variable initialized to front, test for end of list)
1 moves current (current = current.next)
1 examines every element of the list (ignoring flags)
4 two flags for odd/even
1 attempt at one flag
1 attempt at second flag
1 one flag correct
1 second flag correct
3 correctly returns true or false (requires loop AND both flag attempts)
1 attempt (some attempt to combine odd and even results)
2 correct
4 stops at first occurrence of odd/even
2 attempt (one pass through the data with some attempt to return or break
from loop when odd/even found)
2 correctly stops based on two flags (-1 if obob)
Problem #5
solution
public static void mirror(Stack<Integer> s) {
Queue<Integer> q = new LinkedQueue<Integer>();
while (!s.isEmpty())
q.enqueue(s.pop());
while (!q.isEmpty())
s.push(q.dequeue());
while (!s.isEmpty())
q.enqueue(s.pop());
for (int i = 0; i < q.size(); i++) {
int n = q.dequeue();
s.push(n);
q.enqueue(n);
}
while (!s.isEmpty())
q.enqueue(s.pop());
while (!q.isEmpty())
s.push(q.dequeue());
}
2 header (-1 per error, non-void return okay if consistent)
2 construct queue (-1 per error)
4 Basic attempt
2 S -> Q
2 Q -> S
2 attempt to deal with forwards/reverse (separate from loops above, atomic):
1 S -> Q
1 Q -> S
4 expanding loop: some loop doubles the number of values
example: go through q, doing both an enqueue and a push
go through stack, enqueueing each value twice
NOT go through stack, doing both an enqueue and a push
11 Otherwise correct: Simulate for:
bottom [1, 2, 3] top
11 [1, 2, 3, 3, 2, 1]--correct answer
5 [3, 2, 1, 1, 2, 3]--both halves reversed
Notes: Take off -1 for each loop error (e.g., for loop using size() that
processes only half the data)
Problem #6
solution
public ArrayIntList reverseCopy() {
ArrayIntList result = new ArrayIntList(elementData.length);
for (int i = 0; i < size; i++) {
result.elementData[i] = elementData[size - 1 - i];
}
result.size = size;
return result;
}
1 header
2 construct a new ArrayIntList
1 attempt (constructing an array or ArrayIntList)
1 correct (must be same capacity as original)
2 loop over original
1 attempt (some kind of for loop involving size or elementData.length)
1 iterates exactly size times
3 copying values in reverse order
1 result.elementData[something] = elementData[something]
2 correct somethings (-1 if obob, no double jeopardy with loop obob)
1 correctly sets result.size
1 returns their result
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011