===========================================================================
CSC 236            Homework Exercise 4 -- 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:

 -  In order to apply the Master Theorem, not only do we have to satisfy
    the conditions of the theorem, but also the recurrence equation has to
    be in a special form.  For example, the Master Theorem does *not* apply
    to the equation T(n) = T(n-1) + 1.

 -  Sometimes, I encountered proofs that just listed a base case, and an
    inductive step.  For this to have a meaning, you should first say that
    you are proving a statement by induction.  Most importantly, you have
    to explicitly write the statement you are proving, and also say what
    you are doing induction on.


1.  [3 marks]

    Solution elements:

    _S_tructure [1 mark]:  clear attempt to give explicit tight bound,
        either by applying Master Theorem or directly.

    _B_ound [2 marks]:  correct bound, justified correctly (i.e., correct
        and properly justified application of Master Theorem, or correct
        inductive proof of tight bound).


2.  [12 marks]

    (a) [5 marks]

        Solution elements:

        _S_tructure [2 marks]:  clear attempt to perform repeated
            substitution then prove exact value by induction -- Master
            Theorem does not apply.

        _C_losed form [1 mark]:  correct closed-form expression.

        _P_roof [2 marks]:  correct inductive proof of exact expression.

    (b) [2 marks]

        Solution elements:

        _PRE_cond [1 mark]:  correct precondition

        _POST_cond [1 mark]:  correct postcondition

    (c) [5 marks]

        Solution elements:

        _S_tructure [2 marks]:  clear attempt to prove postconditions are
            satisfied for all inputs that meet preconditions, by induction
            on input size.

        _C_orrectness [3 marks]:  correct proof, including appropriate use
            of inductive hypothesis in the proof of the inductive step.