CS 211 Prelim1 Grading Guide:

Problem1:

1a (1pt) no partial credit

1b (2pt)

1c (2pt)
    Mention repeats (1pt)     
    Mention order   (1pt)

1d (1pt)

1e (1pt)

1f (1pt)

1g (1pt)

1h (2pt)
   correctly answer two of the three outputs (1pt)
   correctly answer all three outputs (2pt)

1i (2pt)

1j (2pt)
   We have decided that everyone gets these 2pts. It is announced on the course website. Just 
go to a consultant with your prelim if you were deducted on this question.  

Problem 2 (5pt):

Base case: 1pt
Correct statement of Inductive hypothesis and the goal of Inductive step: 1pt
Correct usage of Inductive hypothesis in the Inductive step: 1pt
Correct math in the Inductive step: 1pt
Conclusion: 1pt

Problem 3 (10pt):

Boundardary conditions for n<d, n==0, n==d: 2pt
Correct usage of recursion: 4pt
Correct usage of the subtraction operator: 3pt
Syntax and style: 1pt

Problem 4 (15pt):

4a: 6 (2pt)
    7 (2pt)
    6 (2pt)
    7 (2pt)
    3 (2pt)
    6 (1pt)
    7 (1pt)
    no partial credits

4b: The answer is error (1pt)
    The reason mentioned that method needs to be specified in interface because the method name
    is bound at compile time. (2pt)

Problem 5 (30pt):

createCircle (15pt):

create the entry node firstNode (3pt)
correct stopping condition in the for or while loop. (generate the right number of nodes) (2pt)
build a singly-linked list (the content of the while loop) (5pt)
connect the tail to the head to form a circle (3pt)
Correct syntax, good comments and style (2pt)

You get five points if you assumed pre-existing non-circular list.

searchCircle (15pt):

Most students actually coded in a style like the following:

Alternative solution:

Node n = firstNode;
if (n.value == 0) return true;    (1) 2pt
n=n.next;                         (2) 2pt
while (n != firstNode) {          (3) 4pt
  if (n.value == 0) return true;  (4) 2pt
  n = n.next;                     (5) 1pt
}
return false;                     (6) 2pt
                                  
(7) Correct syntax, good comments and style 2pt

Explanation:
(1) This is to make sure that the code checks the value of all nodes.
(2) This is to make sure that the code will go into the while loop if there are more than 1 node
(3) This is to stop correctly in the while loop
(4) This is to return true if a node with value 0 is found
(5) Correct stepping in the linked list
(6) Return false if no 0 node is found after going through a cycle of the list
    (It is not right if you return immediately after seeing one node does not have value 0)

You do not have to write the same way as the solution. However, if any of the above six issues
is not properly handled, the corresponding points will be deducted.

Problem 6:

makeTree method (16pt):

switch & peek (1pt)
case for E->int (2pt)
case for E->(E+E) (2pt)
correct usage of recursion (3pt)
correct usage of node type (3pt)
default return (return null;) (1pt)
correct usage of fin methods (2pt)
syntax, comments, style (2pt)

ParseTree toString method (3pt):
root==null case (1pt)
not null case   (2pt)

AddNode toString method (4pt):

Alternative solution:
  return leftExpr.toString() + "+" + rightExpr.toString();

leftExpr correct: (1pt)
rightExpr correct: (1pt)
Correct position and usage of "+": (2pt)

IntNode toString method (2pt):
"" (1pt)
+value (1pt)

Bonus points:
each correct answer is worth 1 point.