CS 211, Fall 2006 Prelim 1 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) half of the people got i) wrong there is some issue with d but I cannot make out the handwriting. It says "several people changed a ???. ??? seems to be something like "value" or "choice"... ========================================================= Question 2 (Induction) 2a and 2b are each worth 10 points. The same grading scheme is used for both 2a and 2b. General: -2 for major gap in algebra -1 for notation abuse (e.g., two different k's) Base Case: 2 for valid base case (k=4 for 2a; root-only for 2b) -1 for extra, unnecessary base cases Induction Hypothesis: 2 for valid induction hypothesis -1 if they say "for all k" -1 if they don't say >= 4 for 2a -1 if they don't label the Induction Hypothesis Inductive Step: 5 for valid inductive step (must use IH correctly) -1 for not labeling inductive step Conclusion: 1 for some kind of satisfactory conclusion Common mistakes: (keep track of these during grading) Not technically a mistake but many solutions used the fact that at level k (with root at level 0) you can have at most 2^k nodes. This made the proofs much harder to write and grade than the ones that used strong induction. No points were deducted. Some tried to prove that h+1 < 2(h+2)-1 in their inductive step... ========================================================= Question 3 (Lists) It's OK if the solution is recursive, but this is harder to do. General: -1 if it's hard to read (e.g., if it's not indented) -1 if notably inefficient 0 no penalty for missing semicolons or braces as long as it's readable (but put them in if they are missing) -4 for casting to a singly linked list -2 no length() (???) -6 for returning a singly linked list. Empty List: 2 points for correctly handling an empty list Singleton List: 2 points for correctly handling a singleton list Reversing: 2 points for reversing the list (based on .next fields) Double Linking: 2 points for correctly setting both .next and .previous Circular: 2 points for correctly linking first and last items Common mistakes: (keep track of these during grading) Again not technically a mistake but many people tried to do this recersively and they lost a lot of points because recursion in this problem is trickier than iteration. ========================================================= Question 4 (Inheritance) 2 points each; no partial credit -3 instead of -4 if both p3.output() and ((A)p3).output() are wrong. Common mistakes: (keep track of these during grading) lots of people got lots wrong ========================================================= Question 5 (Trees) Traversals (5abc) 10 points all together -1 for a trivial mistake (e.g., transposing 2 letters) -3 if one is messed up completely -6 if two are messed up completely -10 if all three are messed up completely -2 if swapped two traversals (i.e., mixed up the definitions) BST (5d) 5 points all together -2 for a trivial mistake in constructing the tree -1 for an addition mistake -2 for correct tree, but no sum -2 if doesn't know definition of leaf 1 if they build some tree and manage to add the leaves BST (5e) +1 per correct tree -1/2 per incorrect tree No negative scores Common mistakes: (keep track of these during grading) What's a BST? some mistakes on a,b,c some sorted the letters ========================================================= Question 6 (Recursion) General: -1 if it's hard to read (e.g., if it's not indented) -1 if notably inefficient 0 no penalty for missing semicolons or braces as long as it's readable (but put them in if they are missing) Base Case: 2 for correct base case (null tree) Nodes: 2 for creating new nodes rather than modifying Recursion: -10 for no recursion at all 4 for swapping left and right subtrees in recursive calls 2 for returning the new tree Common mistakes: (keep track of these during grading) Some people didn't understand what "non destructively" means. Also people confuse "without defining new classes" with "without making any new instances of objects" Some solutions didn't handle the empty tree. =========================================================