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.