<![CDATA[
Problem #1
Preorder traversal 2, 0, 5, 1, 7, 6, 3, 4, 9, 8
Inorder traversal 1, 5, 0, 7, 6, 2, 3, 9, 4, 8
Postorder traversal 1, 5, 6, 7, 0, 9, 8, 4, 3, 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
2. +------------+
| France |
+------------+
/ \
/ \
+------------+ +------------+
| Canada | | Italy |
+------------+ +------------+
\ / \
\ / \
+------------+ +------------+ +------------+
| England | | Germany | | USA |
+------------+ +------------+ +------------+
/
/
+------------+
| Japan |
+------------+
Only partial credit is 2 out of 4 points if just one node is in the wrong
place.
-------------------------------------------------------------------------------
Problem #3
Method Call Contents of List Returned
------------------------------------------------
mystery(grid, 2) [13, 35]
mystery(grid, 3) [23, 52, 22]
mystery(grid, 5) [18, 3, 18, 61]
1 pt for first problem
2 pt for second problem
2 pt for third problem
-1 for order error (just once for the entire question)
-1 for missing number
-1 for extra number
no subproblem can go negative
Problem #4
solution
public Set<Point> removeSorted(Set<Point> data) {
Set<Point> result = new HashSet<Point>();
Iterator<Point> i = data.iterator();
while (i.hasNext()) {
Point p = i.next();
if (p.getX() <= p.getY()) {
result.add(p);
i.remove();
}
}
return result;
}
1 correct header (static is okay, non-void return okay if they return something
of that type)
2 iterate over set and removing sorted points
1 reasonable attempt: 3 of 5 of these mostly right:
* get iterator
* loop using iterator or foreach
* get next value from iterator or foreach
* test for sorted
* call on iterator remove (set remove doesn't count)
1 all correct (requires iterator)
2 constructs and returns set of removed points
1 reasonable attempt: two of these three mostly right (for attempt, TreeSet
is okay)
* construct new set HashSet (if they don't use (), that's syntax)
* add removed points to this set
* return it
1 all correct
Problem #5
solution
public void printLevel(int target) {
if (target < 1) {
throw new IllegalArgumentException();
}
System.out.print("nodes at level " + target + " =");
printLevel(overallRoot, target, 1);
System.out.println();
}
private void printLevel(IntTreeNode root, int target, int level) {
if (root != null) {
if (level == target) {
System.out.print(" " + root.data);
} else {
printLevel(root.left, target, level + 1);
printLevel(root.right, target, level + 1);
}
}
}
1 overall setup: private header with a root parameter and public method calls
private method passing it overallRoot; private header has target as a
parameter and public method passes target
1 correct exception (can't print anything before the exception)
1 base case for null (tests for this, does nothing, always avoids exception)
2 recursive calls on left and right
1 reasonable attempt (some kind of recursive call on left or right)
1 correctly traverses the entire tree up to level (can traverse more)
3 correctly computes level information to form a test (recurses on level + 1 vs
target or recurses on level - 1 vs 1)
1 attempt (requires recursion attempt, some kind of test that could be a
level test)
2 correct (-1 if minor error like obob)
2 prints data for target level
1 attempt (prints root.data and one of: text before recursion, space with
root.data, println after recursion)
1 correct (requires "compute level" attempt, prints correct text before
call, includes spaces, println after, all other calls are print)
Problem #6
solution
public Map<Integer, Set<String>> byUnits(Map<String, Integer> unit
Map<String, Set<String>> enrollments) {
Map<Integer, Set<String>> result = new TreeMap<Integer, Set<String>>();
for (String student : enrollments.keySet()) {
int sum = 0;
for (String course : enrollments.get(student)) {
sum += units.get(course);
}
if (!result.containsKey(sum)) {
result.put(sum, new TreeSet<String>());
}
result.get(sum).add(student);
}
return result;
}
1 header (static is okay)
2 construct and return proper map
1 reasonable attempt: constructing a map with at least 2 of the following 3
things correct: key type Integer, value type Set, set is of Strings
1 all correct: correct generics, map is TreeMap, correct types, map is
returned, must have () in call to new
1 correct loop over students (keySet of enrollments; can be iterator)
3 correct sum for student
1 reasonable attempt to loop over enrollments for this student
1 reasonable attempt to compute the sum of the units
1 all correct (must initialize sum to 0, must loop over
enrollments.get(student)--can be iterator, must add units.get(course) to
sum exactly once for each course)
3 correctly puts into map:
1 reasonable attempt to construct a new set and put a new entry into the
map the first time a new unit total is seen and never again; three of
these mostly right or reasonable attempt for all four:
* constructing a new set of String (can be TreeSet or HashSet)
* a call on put that associates this sum with the new set
* construct a new set only if the map does not contain this key
* code structure will lead them to add this student to the new set once
1 reasonable attempt to add a student to an existing set (code might also
be executed after constructing a new set); both of these mostly right:
* call on result.get(sum) to access the set
* call on add for this set to add the student
1 all correct
Problem #7
solution
public class AdmissionsEntry implements Comparable<AdmissionsEntry> {
private String ID;
private int ratings;
private double total;
private boolean discuss;
public AdmissionsEntry(String ID) {
this.ID = ID;
this.ratings = 0;
this.total = 0.0;
this.discuss = false;
}
public void rate(double rating) {
ratings++;
total += rating;
if (rating >= 4) {
discuss = true;
}
}
public void flag() {
discuss = true;
}
public double getRating() {
if (ratings == 0) {
return 0.0;
} else {
return total / ratings;
}
}
public String toString() {
double rating = Math.round(100 * getRating()) / 100.0;
return ID + ": " + rating;
}
public int compareTo(AdmissionsEntry other) {
if (discuss && !other.discuss) {
return -1;
} else if (!discuss && other.discuss) {
return 1;
} else if (getRating() > other.getRating()) {
return -1;
} else if (getRating() < other.getRating()) {
return 1;
} else {
return ID.compareTo(other.ID);
}
}
}
1 class header
4 fields (1 point each, -1 once if not private, okay to have extra field(s)
get 1 of 2 points for list of ratings instead of count/total)
1 constructor (can rely on defaults for ratings, total, discuss; requires
constructing list of ratings if they are using that approach)
2 rate method
1 reasonable attempt to record this rating in a field
1 all correct (requires ratings and total field or list, has to record the
score in such a way that an average can be computed)
2 correctly flagging students to be discussed (requires flag field)
1 correct flag method OR correctly flags ratings > 4 in rate method OR
reasonable attempt at both
1 correct flag method AND correctly flags ratings > 4 in rate method
2 getRating method
1 reasonable attempt
1 all correct, including doubl return and 0 for no ratings
3 toString
1 reasonable attempt to concatenate id, colon, average rating
1 correctly rounding whatever they are using for rating to 2 digits
1 correct other than rounding (must work when ratings=0 and must be correct
average rating--okay if they call getRating, must include colon but space
is not required)
5 compareTo
1 reasonable attempt to put flagged students first
1 correctly puts flagged students first
1 reasonable attempt to reverse order by ratings when flag matches
1 reasonable attempt to order by ID when flag and ratings match
1 correctly reverses order by ratings when flag matches and correctly
orders by ID when flag and ratings match
notes:
give question leader odd solutions like array of ratings
this is an odd solution that involves having an "average" field instead and
then getRating get be a one-line return of that value. But then rate has to be
written this way:
public void rate(double rating) {
average = (average * ratings + rating) / (ratings + 1);
ratings++;
if (rating >= 4) {
discuss = true;
}
}
This is okay, but if they compute it wrong, they lose both the rate correctness
point and the getRating correctness point because now this one computation has
to work for both.
Problem #8
solutions
public void limitLeaves(int min) {
overallRoot = limitLeaves(overallRoot, min);
}
private IntTreeNode limitLeaves(IntTreeNode root, int min) {
if (root != null) {
root.left = limitLeaves(root.left, min);
root.right = limitLeaves(root.right, min);
if (root.left == null && root.right == null && root.data <= min) {
root = null;
}
}
return root;
}
-------------------------------------------------------------------------------
// solution that returns specific values instead of root
public void limitLeaves(int n) {
overallRoot = limitLeaves(overallRoot, n);
}
private IntTreeNode limitLeaves(IntTreeNode root, int n) {
if (root != null) {
root.left = limitLeaves(root.left, n);
root.right = limitLeaves(root.right, n);
if (root.left != null || root.right != null || root.data > n) {
return root;
}
}
return null;
}
-------------------------------------------------------------------------------
// void solution (not x=change(x))
public void limitLeaves(int min) {
limitLeaves(overallRoot, min);
if (overallRoot != null && overallRoot.left == null &&
overallRoot.right == null && overallRoot.data <= min) {
overallRoot = null;
}
}
private void limitLeaves(IntTreeNode root, int min) {
if (root != null) {
limitLeaves(root.left, min);
limitLeaves(root.right, min);
if (root.left != null && root.left.left == null &&
root.left.right == null && root.left.data <= min) {
root.left = null;
}
if (root.right != null && root.right.left == null &&
root.right.right == null && root.right.data <= min) {
root.right = null;
}
}
}
1 public header
1 overall setup: private header with a root parameter and public method calls
private method passing it overallRoot; private header has min as a parameter
and public method passes min
5 used x = change(x) or equivalent (ok to give "equivalent" to question 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 right are like this)
1 returns root correctly in all cases where root doesn't change
2 base case for root == null
1 attempt (tested this case)
1 correct: requires test, tree not changed in this case, never get a
NullPointerException (could lose this if they set root to null and then
make recursive calls after)
2 recurse on left and right
1 attempt (either one call with min or two calls without)
1 correct (2 calls each with min)
3 removing current node if it's a leaf with data <= min
1 test for this case (some comparison of root.data vs min)
1 reset root to null or return null in this case
1 all correct (test is root.data <= min)
6 removes ancestors of removed leaves when appropriate
2 reasonable attempt (after some recursive call, attempt to potentially
remove this node--could be something that leads to infinite
loop/recursion)
4 correct (normally solved with correct order)
notes:
Give to question leader solutions that avoid x=change(x), that have extra
data structures, that change data fields, that are inefficient (might not be
O(n)) and anything else odd.
solution with void return that set root.left or root.right to null are
considered "look ahead" solutions graded this normally but with this
substituted for x=change(x) points.
5 x = change(x) substitutes
2 correct test on overallRoot being a leaf to be removed AFTER call on
recursive method and code to set it to null
2 correct test on one of root.left or root.right being a leaf to be removed
and code to set it to null
1 correct test on the other one of root.left or root.right being a leaf to
be removed and code to set it to null
note: -1 for each of these that doesn't test for null, but take it off at
most twice
Problem #9
solution
public LinkedIntList removeSmaller() {
LinkedIntList other = new LinkedIntList();
if (front != null && front.next != null) {
if (front.data <= front.next.data) {
other.front = front;
front = front.next;
} else {
other.front = front.next;
front.next = front.next.next;
}
ListNode current1 = front;
ListNode current2 = other.front;
while (current1.next != null && current1.next.next != null) {
if (current1.next.data <= current1.next.next.data) {
current2.next = current1.next;
current1.next = current1.next.next;
} else {
current2.next = current1.next.next;
current1.next.next = current1.next.next.next;
}
current1 = current1.next;
current2 = current2.next;
}
current2.next = null;
}
return other;
}
1 header (lose this if return type is ListNode even if they return a ListNode)
2 constructs and returns other LinkedIntList
1 reasonable attempt (can get this even if they are returning a ListNode)
1 correct (requires call on LinkedIntList constructor, proper return)
2 simples cases: can't get these for no code...each requires a test
1 length 0 case: does nothing and doesn't throw an exception
1 length 1 case: does nothing and doesn't throw an exception
note: should return empty list for each case, -1 once if they return null
3 correct test on adjacent values at least once, as in:
front.data <= front.next.data front.data > front.next.data
current.data <= current.next.data current.data > current.next.data
1 reasonable attempt ignoring equals case
2 correct test (-1 if close, as in correct other than equals case)
2 generous pattern match
1 using curr1/curr2 variables to keep track of a position in each of the
two lists with a loop that changes each
1 resetting at least two "next" fields in a loop
10 other cases (could lose 2 points for not setting final node link to null)
1 length 2
1 length 2
1 length 3
1 length 3
1 length 4
1 length 4
1 length 10
1 length 11
1 length 11
1 length 13
notes:
-1 if they say other when they mean other.front (but only if that raises their
score)
If their tests don't work for the 10 points of other cases, you can fix the
test for both the front of the list case and inside the loop, but then they
lose all 3 of the test points including the attempt point (only apply this rule
if their score goes up).
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. A single correction would involve adding or
deleting a single line of code like curr=curr.next or changing a test for
something like curr!=null to be curr.next!=null (this could be a double-change
to parallel curr1/curr2). Another change to consider is calling a special
method included in the grading program called switchFronts that switches the
fronts of the lists. Any such change costs 5 points and we are willing to make
only ONE such change.
Another example of a change would be if they use a name like "curr" when they
have variables with names like "curr1" and "curr2", so we don't know which one
they mean. That would require a 5-point charge.
Any O(n^2) solutions or odd solutions (new nodes, changing data) go to the
question leader.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011