CS 211, Fall 2005 Prelim 1 Grading Guide ========================================================= Question 1 (True/False) 2 points each; no partial credit ========================================================= 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 (12 for 2a; 10^1 for 2b) -1 for extra, unnecessary base cases Induction Hypothesis: 2 for valid induction hypothesis -1 if they say "for all n" -1 if they don't bound it (>= 12 for 2a; >= 1 or >= 0 for 2b) -1 if they don't label the Induction Hypothesis Inductive Step: 5 for valid inductive step (must use IH correctly) -2.5 for missing a case -1 for not labeling inductive step Conclusion: 1 for some kind of satisfactory conclusion Common mistakes: - no bounds on IH - too many base cases - only doing half the proof on the change one (i.e. what if there was no 4 cent stamp) - not indicating where they used the IH ========================================================= Question 3 (Recursion & Lists) It's unclear exactly what is meant by "even" so anything that removes every other element is OK. It's OK if they make use of a helper method: removeOdd. It's *not* OK if the solution is iterative instead of recursive (an iterative solution is worth at most 3 points). 4 points for base cases: there should be two -3 if one is missing -2 if base case is there, but slightly wrong 2 points for correct recursive call 2 points for linking recursive-result correctly 2 points for correct return value Common mistakes: - Using one base case instead of two - Not linking the recursive calls properly (i.e. returning only on the base-case and not anywhere else) ========================================================= Question 4 (Types) 3 points each; no partial credit ========================================================= Question 5 (Trees) Each part (5a, 5b, 5c) is worth 7 points. 5a: -1 for a trivial mistake (e.g., transposing 2 letters) -3 if one is messed up completely -5 if two are messed up completely -2 if swapped two traversals (i.e., mixed up definitions) 5b: -4 if there are too few nodes (as long as it works) otherwise, all or nothing 5c: -3 for wrong root -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 Common mistakes: mixing up how preorder and postorder traversals work; not correctly inserting nodes into the binary search tree - possibly because of not knowing how a BST insert method works. ========================================================= Question 6 (Recursion) General: -1 for incorrect header for main method (-2 if it's really bad) -1 if not within class with correct name (MainProblem) -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 missing base case -1 for use of == instead of .equals or .length -1 for null instead of empty string Pretty Printing: -1 for println instead of print -1 for forgetting space after each substring Total penalty for lack of pretty printing should be at most -1. It's nice if they have println at the end, but no penalty for not having it. Recursion: -5 for no recursion at all -2 for using args[0] in recursive call instead of entire array -2 for use of class variables -1 if array is updated incorrectly (e.g., they misuse substring) =========================================================