CS211 S05 Final Exam Grading Guide
1. As given in answer key. O(n/2) for (d) - no credit.
2. As given in answer key. List for (d) - no credit.
3. As given in answer key.
4. Base case 2
Inductive case 4
-1 don't say n is odd
-1 don't show where IH is used
-4 don't increment by 2
State conclusion 1
5. As given in answer key.
6. As given in answer key.
7. Knowledge of what a witness pair is, even if argument wrong 2
Correct argument 2
Note: works with either (2,7) or (7,2). No deduction for using another pair if correct.
8. Correct handling of base case 3
Correct handling of inductive case 7 (match 3, non-match 4)
Note: must handle null input if method could call itself recursively with null,
otherwise no deduction for assuming input is nonnull.
Correct nonrecursive method: 2 points total.
9. As given in answer key. No partial credit.
10. As given in answer key, except (a) full credit for ACBDFEGIHJ.
11. Shape of tree correct but 1 or 2 numbers out of place: 2 points total.
Shape of tree correct but more than 2 numbers out of place: 1 point total.
12. Tree does not satisfy AVL invariant: no credit.
Tree correct shape but 2 numbers out of place: 2 points total.
Tree correct shape but more than 2 numbers out of place: no credit
1 error in shape but data in correct order 2 points total
more than 1 error in shape but data in correct order: no credit
13. Correct structure: between calls betweenHelper with extra argument 2
betweenHelper correct base case 2
check for null before recursive call 2
correct form of recursive call left.betweenHelper and right.betweenHelper 2
correct use of compareTo 1
prunes search using node values 1
no deduction for assuming lower < upper (strictly)
no deduction for getting arguments of compareTo backwards
Correct nonrecursive method: 2 points total.
14. As given in answer key. No partial credit.
15. As given in answer key.
1 point deduction for not getting frame title right.