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