Problem 1: 3 pts: Proper base case (-2: attempted, but indices wrong) 3 pts: termination 3 pts: matches element existence (-2: used == or .equals(), or other odd error) 6 pts: recursive calls on left/right -3 if the calls are made, but backwards, -2 wrong comparison -2 no word return, or something reasonable Misc: -4: copied array -1: small other errors -2: calculated mid wrong -15: not binary search Problem 2: 0  - does not resemble quicksort or incomplete 5  - shows high-level structure of quicksort (e.g. partition and recurse) but not executed correctly 8  - mostly correct with slight errors, e.g. stopping recursion when list is sorted 10 - completely correct. considerable leeway was given for partitioning scheme. With some interpolation if falls between these cases. Problem 3: a) 2 pts: properly applies the definition of O(..) to the hypotheses 3 pts: correctly completes the argument 2/5: if just added O(n log n) to each other b) -0.5 for each ordering wrong (i.e. swapping 2 entries is -1) c) 2 points for arguing that the time for the inner loop is essentially linear 2 points for stating that the inner loop is run n^2 times 1 point for stating the O(n^3) complexity d) 3 points for recurrence relation 2 points for correct answer using the above, or arguing via similarity to mergesort -1 if claim it's the same as merge sort Problem 4: In each of the parts: Fully valid: 5/5 If valid traversal, but not with alphabetical node expansion: 2/5. Otherwise, 0/5 Problem 5: 1 point each Problem 6: a) 3 pts for the picture, 2 points for the number Problem 7: 1 point per every 2 correct; OK if backwards. If 1 only 1 wrong, count as -1. Problem 8: Note: no credit should be given for a method if it has the wrong asymptotic complexity 4 points for proper put 4 points for proper get -2 if doesn't consider the case of the key not existing 2 points for proper containsKey 2 points for size 3 points for elements() -1 for minor bugs. Do not take off for improper method names, minor syntactic errors, unless they are so severe as to suggest lack of basic understanding of the language.