<![CDATA[
CSE143 Key and Criteria, Fall 2008
1. Binary Tree Traversals, 6 points.
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. Binary Search Tree, 4 points.
+------------+
| Kirk |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Chekov | | Spock |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Scotty | | Uhuru |
+------------+ +------------+
/ /
/ /
/ /
+------------+ +------------+
| McCoy | | Sulu |
+------------+ +------------+
Problem #3
Solution:
public int purebredOdds() {
return purebredOdds(overallRoot);
}
private int purebredOdds(IntTreeNode root) {
if (root == null || root.data % 2 == 0)
return 0;
else
return 1 + purebredOdds(root.left) + purebredOdds(root.right);
}
1 correct public header
1 private header with root parameter, public method returns result of calling
private with overallRoot
2 base case when root == null
1 reasonable attempt to test for this case
1 correct (returns 0 whenever root is null)
3 base case when root.data % 2 == 0
1 reasonable attempt to test for this case
2 correct (returns 0 whenever root.data is even)
3 recursive case
1 adding two recursive calls on root.left and root.right (generous)
2 correct for odds (requires reasonable attempt at testing for odd,
returns 1 + recurse(root.left) + recurse(root.right))
Problem #4
Solution:
public class AnalyzingDocumentList extends DocumentList {
private Map<Integer, Integer> counts;
private int stateCount;
public AnalyzingDocumentList(int capacity) {
super(capacity);
counts = new HashMap<Integer, Integer>();
counts.put(0, 1);
stateCount = 1;
}
public void add(Document d) {
super.add(d);
stateUpdate();
}
public void add(int index, Document d) {
super.add(index, d);
stateUpdate();
}
public void remove(int index) {
super.remove(index);
stateUpdate();
}
private void stateUpdate() {
stateCount++;
int size = size();
if (!counts.containsKey(size))
counts.put(size, 1);
else
counts.put(size, counts.get(size) + 1);
}
public int totalStates() {
return stateCount;
}
public int sizeCount(int size) {
if (counts.containsKey(size))
return counts.get(size);
else
return 0;
}
}
1 class header
3 fields
2 Map<Integer, Integer> or List<Integer> for counts
1 state count (int) or reasonable attempt to add them up in totalStates
-1 if either is nonprivate
4 constructor
1 header and super(data)
1 initialize counts
2 correctly records initial state
1 attempt (e.g., handles just one of 2 fields)
1 correct
2 totalStates (two possibilities)
2 using a state count field
1 attempt to increment in add/remove method (at least 2 of them)
1 all correct (increments in all 3, returns field)
2 adding up all of the counts
1 reasonable attempt to add them up
1 all correct
3 overriding two add methods and remove
1 at least two of them are overridden
1 at least two of them call the super version
1 all three overridden and call super version
4 correctly handles modifications
1 reasonable attempt in at least one method
1 in at least one method it correctly increments size if seen previously
1 in at least one method it correctly handles a new size (count of 1)
1 same modification code appears in all 3 methods (or 3 calls to private)
3 sizeCount
1 reasonable attempt (method declared, attempt to access their map or list)
1 correct if this is a size we've seen (in map or list)
1 correct (returns 0) if this is a size we haven't seen
Array based solutions go to the question leader.
If they destroy a method they inherited (e.g., size, indexOf): -1, -2, -3 based
on quality (max -3).
Alternate solution to #4 using List<Integer>
public class AnalyzingDocumentList extends DocumentList {
private List<Integer> count;
private int stateCount;
public AnalyzingDocumentList(int capacity) {
super(capacity);
count = new ArrayList<Integer>();
count.add(1);
stateCount = 1;
}
public void add(Document d) {
super.add(d);
stateUpdate();
}
public void add(int index, Document d) {
super.add(index, d);
stateUpdate();
}
public void remove(int index) {
super.remove(index);
stateUpdate();
}
private void stateUpdate() {
stateCount++;
int size = size();
if (size >= count.size())
count.add(1);
else
count.set(size, count.get(size) + 1);
}
public int totalStates() {
return stateCount;
}
public int sizeCount(int size) {
if (size >= 0 && size < count.size())
return count.get(size);
else
return 0;
}
}
Alternate solution to #4 using int[]
public class AnalyzingDocumentList extends DocumentList {
private int[] count;
private int stateCount;
public AnalyzingDocumentList(int capacity) {
super(capacity);
count = new int[capacity + 1];
count[0]++;
stateCount = 1;
}
public void add(Document d) {
super.add(d);
stateUpdate();
}
public void add(int index, Document d) {
super.add(index, d);
stateUpdate();
}
public void remove(int index) {
super.remove(index);
stateUpdate();
}
private void stateUpdate() {
stateCount++;
count[size()]++;
}
public int totalStates() {
return stateCount;
}
public int sizeCount(int size) {
if (size >= 0 && size < count.length)
return count[size];
else
return 0;
}
}
Problem #5
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() {
if (getCalories() == 0)
return 0.0;
else
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
4 fields (1 point each, -1 if not private, okay to have extra field(s) for
calories or fat calories or percent fat)
3 constructor
1 correct header
1 exception
1 sets four fields correctly
1 getName correct
2 getCalories correct
1 attempt
1 correct
3 percentFat correct (don't have to worry about getCalories() == 0)
1 attempt
2 correct (-1 if close--e.g., missing the *100)
2 toString correct
1 includes all four fields
1 correct format
4 compareTo
1 attempt to test difference in percent fat
1 returns negative when this.percentFat < other.percentFat
1 returns positive when this.percentFat > other.percentFat
1 returns name comparison when percentFat equal
Problem #6
Solution:
public void mirror() {
mirror(overallRoot);
}
private void mirror(IntTreeNode root) {
if (root != null) {
IntTreeNode temp = root.left;
root.left = root.right;
root.right = temp;
mirror(root.left);
mirror(root.right);
}
}
1 public header
1 private header with a root parameter (IntTreeNode return is okay if they
actually return root at the end)
1 public method calls private method passing it overallRoot
4 null test
2 attempt (tested this case)
2 correct (tree not changed in this case)
3 recusively mirrors left subtree (don't worry about switching bugs for this)
1 attempt (if you see a call on mirror(root.left), they get this point)
2 correct (always called for non-null root--ok if they prevent a call when
root.left is null)
3 recursively mirrors right subtree (don't worry about switching bugs for this)
1 attempt (if you see a call on mirror(root.right), they get this point)
2 correct (always called for non-null root--ok if they prevent a call when
root.right is null)
7 switches root.left and root.right
1 minimal attempt (e.g., switches root.left.data and root.right.data)
6 all correct (always switches correctly for non-null root); -4 for no use
of temp, -2 for other errors
-10 if they solve it by constructing the mirror image
Problem #7
Solution:
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;
}
}
}
1 header (can be either reverse3 or rotate3)
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)
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
2 Managing to redirect sequence of three next fields somewhere in their code:
before:
+------+------+ +------+------+ +------+------+
| n1 | +--+---> | n2 | +--+---> | n3 | +--+--> other
+------+------+ +------+------+ +------+------+
after:
+------+------+ +------+------+ +------+------+
| n3 | +--+---> | n2 | +--+---> | n1 | +--+--> other
+------+------+ +------+------+ +------+------+
12 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)
2 3-element list
2 4-element list
2 6-element list (1 pt if just first triple is bad)
2 7-element list (1 pt if just first triple is bad)
2 9-element list (1 pt if just first triple is bad)
2 11-element list (1 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 5 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.
Alternate solution to #7 using recursion
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;
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011