===========================================================================
CSC 236            Homework Exercise 2 -- Marking Scheme          Fall 2009
===========================================================================


NOTE TO STUDENTS:

You will find below the marking scheme used for your homework, including
the meaning of marking codes and number of marks associated with each one.
This file also contains my instructions to the marker (so you can get an
idea of how the homework was marked) and the marker's comments about each
question.

Please take the time to read this carefully before you ask questions about
the grading of your homework.


NOTE TO MARKER:

Be picky!  On any homework, it is the responsibility of students to show
that they understand how to solve each problem and to write up their
answers carefully.  At the same time, keep in mind that exercises are worth
only 2% of the final grade and your marking time is very limited, so your
marking must be coarse -- unfortunately, you do not have time to make fine
distinctions, so do not give or take away anything smaller than 0.5 marks.
And remember that marking is not just about evaluating the students's
performances, but also about giving them feedback so that they can learn
from their mistakes -- within the limitations imposed by your marking time,
of course.  This is especially important for students who made numerous or
more serious mistakes, as they are likely to need more feedback in order to
understand why their answers were incorrect.

For each question, I list solution elements with an associated code for
writing on student papers (the letter(s) between underscores _) and a
number of marks.  There are also general errors (with associated codes)
given below, with a maximum number of marks to take off for each type of
general error (as a percentage of the value of the question).  You will
likely encounter other common errors, or maybe decide to break down the
marking scheme further.  Simply make note of these changes/additions to
the marking scheme, and introduce new code letters (or short words) to
allow you to quickly give accurate feedback to the students (both in terms
of what they did wrong and how many marks it cost them).


GENERAL ERRORS (marked negatively, in addition to any other errors):

    _A_rithmetic/_A_lgebra [up to 0.5]:  calculation error

    _N_otation [up to 1]:  incorrect/ambiguous notation

    _V_agueness [up to 1]:  incorrect/unjustified/vague claim


1.  [6 marks]

     +  1 mark for each correct proof structure (2 for each part)

    The question did not clearly specify what "different" meant for proof
    structures, so be somewhat lenient on that point.  Nevertheless,
    students who made only very minor, superficial changes between one
    proof structure and another should get credit for only one of their
    structure (for each part -- it's fine if they re-use similar structures
    from one part to the next).


2.  [4 marks]

    Solution elements:

    _F_ormat [1.5 marks]:  correct proof structure (definition of
        predicate, base case, inductive hypothesis, inductive step,
        conclusion), independently of proof correctness

    _P_redicate [0.5 marks]:  correct definition for predicate P(s)

    _B_ase [0.5 marks]:  correct proof of base case

    _H_ypothesis [0.5 marks]:  correct inductive hypothesis

    _S_tep [1 mark]:  correct proof of inductive step
        (0.5 for correct idea, 0.5, for correct write-up)


Marker's Comments / Error Codes:

 -  Error code "+":  In Question 1, Induction for the *positive* even
        numbers only: -0.5 mark

 -  Please use font size 12pt!

 -  General:  If you applied structural induction without defining
        explicitly the set, i.e., Question 1(c): -0.5 mark

 -  General:  The base case of the induction is not correct, i.e., the empty
        set for Question 1(c) or Question 2: -0.5 mark.

 -  Question 1:  Instead of using two different induction structures, used
        two different definitions of P(n): -1 mark for each

   [Instructor's comment:
    There was a misunderstanding between myself and the marker about this
    -- changes to P(n) were legitimate, but I did not state this in my
    marking scheme.  To correct this, I decided to simply give an extra +2
    to everyone -- up to a maximum of 10.  The posted grades reflect this
    adjustment.]

 -  Question 1 (a):  Induction over all Z instead of even integers:
        -0.5 marks

 -  Question 1 (c):  "P(S) = {a_1, a_2, ... , a_n}" is incorrect: P(S) is
        not a set, it's a predicate.

 -  Question 1 (c):  Used structural induction, but didn't define the set
        of subsets of integers recursively: -0.5 marks

 -  Question 1 (c):  If S is a set in P(S), you can't write P(x) where x is
        a natural number.  You cannot say "S + 1" where S is a set.