===========================================================================
CSC 236            Homework Exercise 2 -- Marking Scheme        Winter 2008
===========================================================================


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 1.5% of the final grade, so your marking should be somewhat coarse.

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 10%]:  calculation error

    _N_otation [up to 20%]:  incorrect/ambiguous notation

    _V_agueness [up to 20%]:  incorrect/unjustified/vague claim

General marker's comments:  Keep notation consistent.  Don't say b = n,
    when n is perfectly sufficient.


(a) [3 marks]

    Solution elements:

    _C_onjecture [2 marks]:  correct conjecture, stated clearly and
        precisely -- mark the rest of the proof independently of the
        correctness of the conjecture (though it's likely to affect the
        correctness of either the base case or the inductive step).

    _P_redicate [1 mark]:  clear, precise, and correct definition of
        predicate P(n) for the following proofs.

    Marker's comments:  Be precise!  "It requires n-1 operation" is vague.
        Does it require at least n-1 operations?  Exactly n-1 operations?
        In the predicate, state that it requires n-1 operations regardless
        of the order of operations -- otherwise, the Inductive Step cannot
        assume arbitrary ordering.


(b) [6 marks]

    Solution elements:

    _F_ormat [1 mark]:  correct proof structure (definition of predicate,
        base case, inductive hypothesis, inductive step, conclusion),
        independently of correctness of the proof itself.

    _B_ase case [1 mark]:  correct proof of base case.

    _IH_ypothesis [1 mark]:  correct simple inductive hypothesis.

    _IS_tep [3 marks]:  correct proof of inductive step -- in particular,
        correct way to reduce P(n+1) to P(n).

    Expected errors:

    _D_irect proof [-1 mark]:  step does not make use of hypothesis.

    Marker's comments:  At the very least, clearly have the 5 steps listed
        -- even if you are not sure about the contents of each step.  You
        can't assume a_{n+1} is the last/first number in the list of
        multiplication operations.


(c) [6 marks]

    Solution elements:

    _F_ormat [1 mark]:  correct proof structure (definition of predicate,
        base case, inductive hypothesis, inductive step, conclusion),
        independently of correctness of the proof itself.

    _B_ase case [1 mark]:  correct proof of base case.

    _IH_ypothesis [1 mark]:  correct complete inductive hypothesis.

    _IS_tep [3 marks]:  correct proof of inductive step -- in particular,
        correct way to break up P(n) into statements about smaller values
        of n for which IH applies.

    Expected errors:

    _D_irect proof [-1 mark]:  step does not make use of hypothesis.

    _S_mple induction [-2 marks]:  proof is nothing but a rewrite of
        simple induction argument, i.e., does not make use of complete
        induction -- in this case, be particularly picky about exact form
        of inductive hypothesis (structure of proof should clearly be
        complete induction, even if inductive step does not make use of
        full inductive hypothesis).

    Marker's comments:  By and large better than the simple induction.
        Careful again with quantifiers.