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