======================================================================
     Faculty of Applied Science and Engineering, University of Toronto
               CSC181: Introduction to Computer Programming, Fall 2000

Second Term Test Marking Scheme
======================================================================

----------
Question 0
----------

Scheme:

* (-1/-2): Student number not written on every page.

Comments:

* These are essentially free marks. I'm glad more people took them
  this time around (compared to the first term test).

----------
Question 1
----------

Scheme:

A (-1): Does not apply 'free' to 'l' itself
B (-1): Syntax error
C (-1/-2): Logical error
D (-1): Invalid pointer use
F (-1): Invalid function parameter
G (-1): Invalid type

Comments:

* Generally well done, although a lot of people confused ListPtr with
  ListNodePtr.

----------
Question 2
----------

Scheme:

A (-1): Does not handle empty tree case (when r == NULL)
B (-1/-2): Logical error
C (-1): No return value
D (-1): Inefficient
E (-1): Does not handle case where r->key contains minimum
F (-1): Syntax error

Comments:

* Generally well done. Students who got penalty D did not seem to
  realize that only the left subtree is relevant in finding the
  minimum key of a BST.

----------
Question 3
----------

Scheme:

A (-1): Does not find leftmost character (using strchr)
B (-1): Does not find rightmost character (using strrchr)
C (-1): Does not check if strchr returns NULL
D (-1): Does not check if strrchr returns NULL
E (-1): Does not check if end >= start
F (-1): Does not copy characters into s
G (-1): Does not copy correct number of characters into s
H (-1): Does not append null character to end of characters in s
I (-1): Does not handle trivial case (result is empty string)
J (-1): Returns incorrect pointer (s)
K (-1): Uses extra memory
L (-1): Misuses string function
M (specified): Logical error
N (specified): Incomplete
P (-1): Memory leak
Q (-1): Modifies ct
X (specified): Syntax error

Comments:

* Performance was across-the-board on this question.

* Note that the question says, "You cannot use any loops or
  recursion." If you did use either of these, then you lost a lot of
  marks on the question, if not all of them.

----------
Question 4
----------

Scheme:

A (-1): Does not test for base/recursive case
B (-1/-2): When x's right subtree is non-empty, does not find minimum
C (-1): When x's right subtree is empty, does not travel up tree
D (-1/-2): From C, does not test for root (x->parent == NULL)
E (-1/-2): From D, does not test whether parent->key > x->key or
		   current == parent->right
F (-1/-2): Returns incorrect pointer
X (specified): Other error

Comments:

* Performance was across-the-board on this question.

----------
Question 5
----------

Scheme:

* (1/2/3/4/5): Correctly visits each element in the list
* (1/2/3/4/5): Correctly detects duplicates
* (1/2/3/4/5): Correctly removes and frees nodes with duplicates

Comments:

* Performance was across-the-board on this question.

* The front of the test booklet advises you to comment long or tricky
  code. When answering a question like this, you should certainly do
  that. It is not a trivial piece of code, and for your own sake, you
  should be able to describe exactly what you are doing so you can
  convince yourself that your answer is correct. Even a one- or
  two-line comment summarizing what each loop does, or what each
  significant block does can help you gather your thoughts. And of
  course, it helps the marker understand your code, and allows them to
  give partial credit if an answer is deemed to be incorrect.

----------
Question 6
----------

Scheme:

A/B (-1/-2): Incorrect base case(s) for computing one number
C (-1): Continuing from A and B, incorrect return value for base case
D/E (-1/-2): Incorrect recursive case for computing one number
F (-1): Incorrect base case for recursive row printing function
G (-1/-2): Incorrect recursive call to row printing function
H (-1): Does not print out number in triangle
I (-1): Incorrect base case for recursive triangle printing function
J (-1/-2): Incorrect recursive call to recursive triangle printing
		   function
K (-1): Does not print "row..."
L (-1/-2): Incorrect call to row printing function
M (-1): Does not print newline ("\n")
N (-1): Uses factorial to compute number
O (-1/-2): Off-by-one error
P (specified): Uses loops

Comments:

* Generally well done.

* J and O were very common errors. Regarding J, note that for any
  recursive call that prints out a sequence, the placement of the
  recursive call relative to the printing statement(s) determines
  whether the sequence is printed forwards or backwards. The O penalty
  could have been avoided with careful tracing.

* Note that question says you cannot use any loops, global variables
  or auxiliary data structures. If you used any of these, then you
  lost a lot of marks on the question, if not all of them. Variables
  declared "static" were treated as global.