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) =========================================================