<![CDATA[
Problem #1
Preorder traversal 2, 6, 0, 1, 3, 5, 7, 9, 8, 4
Inorder traversal 0, 6, 3, 1, 5, 2, 7, 8, 9, 4
Postorder traversal 0, 3, 5, 1, 6, 8, 4, 9, 7, 2
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
solutions
public void printTwos(int n) {
if (n < 1)
throw new IllegalArgumentException();
else if (n % 4 == 0) {
System.out.print("2 * ");
printTwos(n / 4);
System.out.print(" * 2");
} else if (n % 2 == 0) {
System.out.print("2 * ");
printTwos(n / 2);
} else {
System.out.print(n);
}
}
public static void printTwos(int n) {
if (n < 1)
throw new IllegalArgumentException();
printTwos(n, 0);
}
public static void printTwos(int n, int numPrinted) {
if (n % 2 != 0)
System.out.print(n);
else if (numPrinted % 2 == 0) {
System.out.print("2 * ");
printTwos(n / 2, numPrinted + 1);
} else {
printTwos(n / 2, numPrinted + 1);
System.out.print(" * 2");
}
}
1 correct header
1 correct exception
2 base case for odd numbers
1 test for this case or test for 1 (could be an else with a test for even)
1 print n in this case (println is okay here)
5 recursive cases
1 a recursive case testing n%2==0 or n%4==0 and recursing on n/2 or n/4
1 a 2nd recursive case testing n%2==0 or n%4==0 and recursing on n/2 or n/4
1 correctly prints 2 * recurse(n/4) * 2 when n%4==0
2 correctly prints 2 * recurse(n/2) when n%2==0 && n%4!=0 (n/2 % 2 != 0)
(-1 if test is incomplete, e.g., testing n % 2 == 0)
notes:
-1 if they use println but only if they got some printing correctness point
-1 if they include a call on printTwos in a println but only if they got some
recursive case correctness points
Problem #3
Statement Output
------------------------------------------------------------
var1.method2(); Pig 2
var2.method2(); Dog 2
var3.method2(); Dog 2
var4.method2(); compiler error
var5.method2(); Horse 2
var6.method2(); Pig 2
var1.method3(); Cat 3/Pig 2
var2.method3(); compiler error
var3.method3(); compiler error
var4.method3(); compiler error
var5.method3(); Cat 3/Horse 2
var6.method3(); Cat 3/Pig 2
((Pig)var5).method1(); runtime error
((Cat)var3).method3(); Cat 3/Dog 2
((Cat)var4).method1(); compiler error
((Pig)var1).method1(); Horse 1/Dog 2
((Horse)var4).method1(); Horse 1/Dog 2
((Cat)var2).method3(); runtime error
((Horse)var3).method1(); runtime error
((Dog)var4).method2(); Horse 2
Problem #4
solution
public static 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;
}
}
1 header
1 constructs temporary queue using generics correctly
1 special test for size < 2 or equivalent
1 basic idea: S -> Q, Q -> S, comparing adjacent values
-------------------------------------------------------------------------------
no more points if student doesn't have basic idea
2 four loops to get correct order: S -> Q, Q -> S, S-> Q, Q -> S
1 attempt
1 correct (can get this even if they return early)
1 compare adjacent values correctly (all pairs, correct order)
2 restores stack in all cases (normally lose this if they return early)
1 attempt (flag or code to restore before returning)
1 correct
1 always returns appropriate values (flag or true/false)
Problem #5
solution
public void printLeaves() {
if (overallRoot == null)
System.out.println("no leaves");
else {
System.out.print("leaves:");
printLeaves(overallRoot);
System.out.println();
}
}
private void printLeaves(IntTreeNode root) {
if (root != null)
if (root.left == null && root.right == null)
System.out.print(" " + root.data);
else {
printLeaves(root.right);
printLeaves(root.left);
}
}
1 overall setup: correct public/private headers, public method passes
overallRoot to private method
1 prints "no leaves" when overallRoot is null and in no other cases (don't
worry about print versus println for this point)
1 base case for null (tests for this and prevents any NullPointerException)
3 handles leaf nodes properly
1 reasonable attempt to test for this case
1 prints root data for some leaves (ignore spacing, requires test attempt)
1 prints root data for all leaves and just leaves with spaces
3 recursive calls on left and right
1 reasonable attempt (some kind of recursive call on left or right)
1 correctly traverses the entire tree
1 traverses right-to-left
1 other formatting details correct (prints "leaves:" before call, each call
produces exactly one line of output)
Problem #6
solution
public static Map<String, Set<String>> convert(Set<String> numbers) {
Map<String, Set<String>> result = new TreeMap<String, Set<String>>();
for (String s : numbers) {
String exchange = s.substring(0, 3);
String digits = s.substring(4);
if (!result.containsKey(exchange)) {
result.put(exchange, new TreeSet<String>());
}
result.get(exchange).add(digits);
}
return result;
}
1 header
2 construct and return proper map
1 reasonable attempt: map of strings to sets
1 all correct (correct generics, correct return, map is a TreeMap, must
have () in call to new)
1 loop over set
1 properly split the string (s.split("-") okay)
3 add a new set to map when key is first seen
1 reasonable attempt to test for this case
1 reasonable attempt to construct new set in this case
1 all correct (correct generics, set is TreeSet, () in call to new,
efficient--constructs sets only in this case)
2 adds suffix to existing set assuming key is there
1 reasonable attempt (getting something from the map that they then add to)
1 all correct
notes:
if they are missing () in call to new, don't take it off twice
Problem #7
solution
public class FoodData implements Comparable<FoodData> {
private String name;
private double fat;
private double carbs;
private double protein;
public FoodData(String name, double fat, double carbs,
double protein) {
if (fat < 0 || carbs < 0 || protein < 0)
throw new IllegalArgumentException();
this.name = name;
this.fat = fat;
this.carbs = carbs;
this.protein = protein;
}
public String getName() {
return name;
}
public double getCalories() {
return 9 * fat + 4 * (carbs + protein);
}
public double percentFat() {
return 100.0 * (9 * fat / getCalories());
}
public String toString() {
return name + ": " + fat + "g fat, " + carbs +
"g carbohydrates, " + protein + "g protein";
}
public int compareTo(FoodData other) {
double difference = percentFat() - other.percentFat();
if (difference < 0)
return -1;
else if (difference > 0)
return 1;
else
return name.compareTo(other.name);
}
}
1 class header
2 fields (0.5 points each but round up, -1 if not private, okay to have extra
field(s) for calories or fat calories or percent fat)
2 constructor
1 exception
1 correct header and sets four fields correctly
1 getName correct
3 getCalories and percentFat correct
1 reasonable attempt at getCalories
1 reasonable attempt at percentFat
1 both correct (ignore case where getCalories() == 0)
2 toString correct
1 includes all four fields
1 correct format
4 compareTo
1 primary comparison is for some kind of fat comparison
1 correctly computes difference of percent fat and returns int (using
if/else or (int)Math.signum; hard to get this unless they make calls on
percentFat)
1 puts lower percent fat first
1 all other aspects correct (header, alphabetical name comparison when
percentFat equal)
Notes:
ignore any code for rounding
Problem #8
solution
public void makeFull() {
overallRoot = makeFull(overallRoot);
}
private IntTreeNode makeFull(IntTreeNode root) {
if (root != null) {
root.left = makeFull(root.left);
root.right = makeFull(root.right);
if (root.left == null && root.right != null)
root = root.right;
else if (root.left != null && root.right == null)
root = root.left;
}
return root;
}
1 overall setup: public/private headers (private needs root), public calls
private passing overallRoot
2 root == null case
1 attempt
1 correct
2 Eliminating 1-child nodes
1 reasonable attempt for one of the two 1-child cases
1 correctly resets root for both 1-child cases
STOP HERE if they don't get 1-child node attempt (don't be shy about asking
question leader if something qualifies as attempt)
5 x = change(x) used correctly
1 return type for private method
1 return root in private
1 overallRoot = makeFull(overallRoot)
1 root.left = makeFull(root.left)--all such calls
1 root.right = makeFull(root.right)--all such calls
1 2-child case works (recursive calls)
1 leaf case works (unchanged)--requires tests
3 recursive calls are made for 1-child cases
1 exist
2 before assignment or as part of assignment (root = makeFull(root.left))
Problem #9
solutions
public void reverse3() {
if (front != null && front.next != null &&
front.next.next != null) {
ListNode temp = front;
front = front.next.next;
ListNode temp2 = front.next;
front.next = temp.next;
temp.next.next = temp;
temp.next = temp2;
while (temp.next != null && temp.next.next != null &&
temp.next.next.next != null) {
temp2 = temp.next;
temp.next = temp.next.next.next;
temp = temp2;
temp2 = temp.next.next.next;
temp.next.next.next = temp.next;
temp.next.next = temp;
temp.next = temp2;
}
}
}
public void reverse3() {
front = reverse3(front);
}
private ListNode reverse3(ListNode lst) {
if (lst != null && lst.next != null && lst.next.next != null) {
ListNode temp = lst;
lst = lst.next.next;
ListNode temp2 = lst.next;
lst.next = temp.next;
temp.next.next = temp;
temp.next = temp2;
temp.next = reverse3(temp.next);
}
return lst;
}
1 header
2 generous pattern matching
1 attempt to rearrange links for first 3 values:
requires resetting front
requires resetting at least two ".next" fields
normally comes before loop
1 attempt at a loop to rearrange links for later sequences (or recursive
equivalent):
requires a current, test on current or current... becoming null
requires resetting at least two ".next" fields
3 Simple cases
1 works (does nothing) for empty list (requires test)
1 works (does nothing) for 1-element list (requires test)
1 works (does nothing) for 2-element (requires test)
7 Works for specific cases (if you think they have a bug that is not caught by
the test cases, ask the question leader what points to deduct)
1 3-element list
1 4-element list
1 5-element list
1 6-element list (0.5 pt if just first triple is bad)
1 7-element list (0.5 pt if just first triple is bad)
1 9-element list (0.5 pt if just first triple is bad)
1 11-element list (0.5 pt if just first triple is bad)
We have a general rule that if you can fix one problem and it suddenly works,
then we make that fix and charge them 4 points. If this gives someone a higher
score, you can grade it that way. But don't spend too much time trying to
figure out their mistakes.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011