<![CDATA[
Problem #1
Preorder traversal 4, 5, 2, 9, 3, 7, 6, 0, 1, 8
Inorder traversal 2, 9, 5, 3, 7, 4, 0, 6, 8, 1
Postorder traversal 9, 2, 7, 3, 5, 0, 8, 1, 6, 4
2 points each, only partial credit is if the sequence matches the right answer
other than one single error (missing number, wrong number, transposed pair)
problem #2
+------------+
| Karl |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Chris | | Simon |
+------------+ +------------+
/ \ \
/ \ \
/ \ \
+------------+ +------------+ +------------+
| Anton | | John | | Zoe |
+------------+ +------------+ +------------+
/
/
/
+------------+
| Zach |
+------------+
Only partial credit is 2 out of 4 points if just one node is in the wrong
place.
Problem #3
solution
public int oddDepthSum() {
return sum(overallRoot, 1);
}
private int sum(IntTreeNode root, int depth) {
if (root == null)
return 0;
else if (depth % 2 == 0)
return sum(root.left, depth + 1) + sum(root.right, depth + 1);
else
return root.data + sum(root.left, depth + 1) +
sum(root.right, depth + 1);
}
1 correct public header && private header with root parameter && public method
returns result of calling private with overallRoot
1 works (returns 0) when overallRoot is null
2 base case when root == null for nonempty trees
1 reasonable attempt to test for this case
1 correct (no NullPointerException, returns 0 whenever root is null)
6 recursive cases
1 their answer includes recursive call on root.left and recursive call on
root.right
3 adds root.data to their sum when level is odd
2 attempt (must pass extra int parameter updated with +1 or ++ or
extra boolean parameter updated with not)
1 correct
2 actually works to compute the sum (requires previous attempt)
Problem #4
solution
class TeamData implements Comparable<TeamData> {
private String name;
private int solved;
private int totalTime;
private int problems;
public TeamData(String name, int problems) {
this.name = name;
this.problems = problems;
this.totalTime = 0;
this.solved = 0;
}
public void success(int problem, int time) {
solved++;
totalTime += time;
}
public String toString() {
return name + " solved " + solved + " of " + problems + " in "
+ totalTime + " minutes";
}
public int solved() {
return solved;
}
public int time() {
return totalTime;
}
public double percentCorrect() {
return 100.0 * solved / problems;
}
public int compareTo(TeamData other) {
if (solved != other.solved)
return other.solved - solved;
else
return totalTime - other.totalTime;
}
}
1 class header
4 fields (1 point each, -1 once if not private, okay to have extra field(s))
2 constructor
1 correct header
1 all fields set apropriately (can rely on defaults for totalTime, solved)
2 solved and time methods
1 reasonable attempt (at least one method completely correct or two methods
that are each partially correct)
1 all correct
2 percentCorrect method
1 reasonable attempt (exists, divides solved by problems)
1 correct
2 success method
1 reasonable attempt (updates at least one of the two fields)
1 all correct
2 toString
1 reasonable attempt (exists, includes at least 2 of the 4 fields)
1 all correct, including format
5 compareTo
1 primary comparison is for problems solved
1 compares times when problems solved is equal
2 correct comparison for problems solved (most people will miss this)
1 all other aspects correct (header, time comparison)
Problem #5
solution
class ExtendedTeamData extends TeamData {
private int[] times;
private int[] failed;
public ExtendedTeamData(String name, int problems) {
super(name, problems);
times = new int[problems];
failed = new int[problems];
}
public void success(int problem, int time) {
times[problem] = time;
super.success(problem, time + failed[problem] * 20);
}
public void fail(int problem) {
failed[problem]++;
}
public String detailString() {
String result = "solved:";
for (int i = 0; i < times.length; i++)
if (times[i] > 0) {
result += " " + i + " (" + times[i];
if (failed[i] > 0)
result += "+" + failed[i] * 20;
result += ")";
}
return result;
}
}
1 class header
2 correct use of data structures: these should be difficult to get, but then
we're going to assume that whatever they do works. They should lose both of
these points if one or both of their data structures are in their TeamData
class.
1 Know how to use at least one such structure. Requires:
* appropriate structure (int[], Map<Integer, Integer>, List<Integer>)
* at least one correct initialization of their structure somewhere
* at least one correct put into the structure somewhere
* at least one correct get from their structure somewhere
1 Really know how to use structures (always use them correctly). Requires:
* two appropriate structures
* fail method includes at least one put
* success method includes at least one put
* detailString method includes at least one get and correct loop bounds
4 fields
2 field to store count of failed attempts (map, array, list)
1 declared
1 initialized in a proper place (can be outside constructor)
2 field to store problem times (map, array, list)
1 declared
1 initialized in a proper place (can be outside constructor)
1 constructor header and call on super(name, problems)
2 fail method
1 exists, correct header
1 records failed attempt for given problem (requires failed field)
5 success method
4 calling super.success
1 correct call on super.success when no failed attempts for problem
3 adds penalty to time when there are failed attempts for a problem
1 attempt (e.g., increment private superclass time)
2 correct (penalty included in call on super.success)
1 records time (requires time field)
5 detailString method
1 loop over problems
1 append problem # and time if solved (requires solved/times field)
2 appends penalty, if any (requires failed field)
1 correct test to append penalty only if there is one
1 appends correct string
1 overall structure: method header, result string that starts with
"solved:", return result string
Problem #6
solution
public void stretch() {
overallRoot = stretch(overallRoot);
}
private IntTreeNode stretch(IntTreeNode root) {
if (root != null) {
root.left = stretch(root.left);
root.right = stretch(root.right);
if (root.left != null && root.right == null)
root = new IntTreeNode(1, root, null);
else if (root.left == null && root.right != null)
root = new IntTreeNode(1, null, root);
}
return root;
}
1 public header
1 private header with a root parameter and public method calls private method
passing it overallRoot
1 works (does nothing) when overallRoot is null (based on test)
5 used x = change(x) (if you think they didn't need it, show to quest leader)
1 overallRoot = recurse(overallRoot)
1 private method has return type IntTreeNode
1 root.left = recurse(root.left) (at least one && all left are like this)
1 root.right = recurse(root.right) (at least one && all left are like this)
1 private method returns an IntTreeNode in at least one case
3 base case when root = null for nonempty trees
1 attempt (tested this case)
2 correct (tree not changed in this case)
3 recursively stretching subtrees
1 attempt: calls on stretch(root.left) and stretch(root.right)
2 correct: stretch in all appropriate cases, no order problems
6 adding new nodes
1 attempt to test for this case (test if left or right is null)
1 correct tests (has to exclude leaf case)
2 construct a new node in this case (requires test attempt)
1 call on node constructor is correct (includes 1, places old node in
correct place)
1 always reset root to new list node (or returns it)
Problem #7
solution
public void markMultiples(int n) {
if (n <= 0)
throw new IllegalArgumentException();
if (front != null) {
ListNode current = front; // tricky Stuart sets current before
// resetting front
if (front.data % n == 0)
front = new ListNode(0, front);
while (current.next != null) {
if (current.next.data % n == 0) {
current.next = new ListNode(0, current.next);
current = current.next.next;
} else
current = current.next;
}
}
}
1 header
2 exception
1 attempt
1 correct
1 works (does nothing) for empty list (requires test)
6 correctly inserts at front of list
2 attempt: test if front.data % n == 0 && (make a new node || reset front)
2 correct: correctly inserts 0 at front of list when front.data % n == 0
2 test front.data % n == 0 && reset front && current set to OLD front
(for a prev/curr solution, prev must be set to old front)
10 inserts in rest of list
2 generous: have a loop with a curr, test for null, curr = curr.next
--------------------------------------------------------------------------
all of the remaining points require basic idea
2 basic idea: test for <something>.data % n == 0 && construct new node
2 looking one ahead (curr.next) or using a prev/curr approach && correct
loop bounds (-1 if obob)
2 correct insertion of 0; one of these (or equivalent):
if (current.next.data % n == 0)
current.next = new ListNode(0, curr.next);
if (current.data % n == 0)
prev.next = new ListNode(0, curr.next);
2 special update for curr or prev/curr if you insert (nobody should end up
pointing to the new node)
Recursive solutions go to question leader.
In this question we will make limited use of a dangerous grading concept known
as "transformation." For example, what if a student has a perfect solution
other than the fact that they were missing "current = current.next" inside
their loop? The criteria often award them 0 points because nothing works. But
perhaps the student just made a stupid mistake and actually knows quite a bit.
We will keep a table of transformations that you can apply. You can apply only
ONE transformation unless you get the approval of the question leader.
Standard transformations:
Penalty Problem
------------------------------------------------------
3 test for multiple is (number / n == 0)
3 test for multiple is (number % 2 == 0)
3 loop update is current = current.next.next;
5 loop is missing current = current.next
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011