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.