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


1.  [7 marks]

    Solution elements:

    _F_ormat [2 marks]:  clear attempt to give a recurrence relation
        defined appropriately (including meaning of n, and justification
        for each number of steps).

    _R_ecurrence [3 marks]:  correct recurrence.

    _J_ustification [2 marks]:  good justification for recurrence.

    Marker's comments:

     -  For Format, 1 mark for "n=y", 1 mark for having a justification.

     -  For Recurrence, 1 mark for the base case, 2 marks for the general
        case.


2.  [8 marks]

    Solution elements:

    _F_ormat [1 mark]:  clear attempt to substitute repeatedly, starting
        from T(n) and ignoring rounding, until a pattern is identified and
        substituted into to reach a base case.

    _S_ubstitution [2 marks]:  correct substitution.

    _P_attern [2 marks]:  correct pattern identified.

    _B_ase _C_ase [1 mark]:  correct number of substitutions to reach a
        base case.

    _C_alculations [2 marks]:  correct simplifications and final answer.

    Marker's comments:

     -  Many people substituted incorrectly.  Most popular was forgetting
        to write n/4 for the "n" term when computing T((n/4)/4).  Other
        mistakes in arithmetic were popular, too -- nothing difficult, just
        a failure to pay attention to the specifics of powers (e.g.,
        mistaking 2^{i-1} for 2^i).

    Instructor's comment:

     -  Performing substitution correctly is something that I expect
        everyone to be able to do with no trouble at all, *especially* when
        it's on an exercise (without the time pressure of a test, and when
        you can work out the arithmetic in more detail).  If you have any
        doubts at all about how to do this, please ask me questions
        *before* you have to hand in work where it's going to be worth
        marks!