CS 211, Fall 2006
Prelim 2 Grading Guide - Preliminary Version
(it is expected to change somewhat during grading)
=========================================================
Question 1 (True/False)
2 points each; no partial credit
Common mistakes: (keep track of these during grading)
=========================================================
Question 2 (Heaps)
5 points for each of a, b, and c.
Mostly all or nothing, unless you can see where they made a trivial
copying mistake (-1 for each such mistake).
+1 in (b) if 105 ends up at position 1 in the array (with 0 unused).
-1 for not drawing array
-1 if do removes on heap in B
-3 only did one getMax
Common mistakes: (keep track of these during grading)
=========================================================
Question 3 (Data Structures)
Five points for each part.
General: There should be enough detail that you can tell what
they're doing, but long explanations aren't required.
-1 if it's hard to read
-1 if they neglect to mention expected or worst-case
-4 if they use a scheme with a lesser time bound
-1 if time bound wrong
(3a): Anything mentioning nested loops or compare all pairs should
be OK.
(3b): If they use a heap, it's completely wrong.
-2 if they don't mention *balanced* BST
(3c): They have to use a hash table here.
-4 if made hashtable min <-> max
-3 just saying dictionary without implementation details
-2 for everything in bucket
-2 not explaining some part
-3 half explanation is wrong
Common mistakes: (keep track of these during grading)
=========================================================
Question 4 (Data Structures)
Five points for each part.
General: There should be enough detail that you can tell what
they're doing, but long explanations aren't required.
-1 if it's hard to read
(4a): These are all standard operations for a balanced BST.
-2 if they don't mention *balanced* BST
(4b): They need to provide some kind of explanation.
-3 if they don't mention the necessary extra variable at all
-2 if they don't mention updating it during Insert
0 it's OK to use an array instead of a linked list
(although it can potentially overflow)
-3 if they use a hash table
(it doesn't satisfy the *worst-case* bound)
(4c): They need to provide some kind of explanation.
-3 if they don't mention the necessary extra variable at all
-2 if they don't mention updating it during Insert
-3 if they use something other than a hash table
(it can't satisfy the time bound requirements)
(4d): Sorted array is the only choice here, but they don't need to
provide much explanation (although they should mention Binary
Search), since the operations are pretty standard.
-3 if they use a sorted linked list
(GetMax is fast enough, but they need Binary Search)
-3 if they use a BST
(Can't do a series of GetMax ops in the required time)
-1 if they use a sorted array, but don't mention Binary Search
Common mistakes: Max Heap in part a, forgot to update min value
when inserting
=========================================================
Question 5 (Big-O)
Five points for each part.
(5a):
-3 if they use limits instead of providing a witness pair
(because it's required by problem statment)
+1 for clearly indicating True
(because it's required by problem statment)
+2 for stating a valid value for N
(any value works as long as they specify a value)
+2 for stating a valid value for c
(it must be k or larger)
(5b):
+1 for clearly indicating False
+2 for defining f and g as functions that satisfy the bounds
+2 for defining them so that f clearly grows faster than g
-5 wrong T/F no partial credit
-1 Math error (eg = instead of <=)
-1 proof not precise
Common mistakes: true for n <= c nlogn
=========================================================
Question 6 (Sorting)
Five points for each part.
General:
-2 if they exclude a sort that should be included
-2 if they include a sort that should be excluded
Common mistakes: (keep track of these during grading)
=========================================================