===========================================================================
CSC 236           Homework Assignment 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.

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/terminology

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


1.  [26 marks]

    _S_tructure [6 marks]:  clear attempt to derive separate lower/upper
        bounds by repeated substitution, then prove them by induction
        (including the inductive structure of those proofs).

    _L_ower _B_ound _S_ubstitution [3 marks]:  correct substitution (or use
        of Master Theorem) for lower bound.

    _L_ower _B_ound [2 marks]:  correct lower bound.

    _L_ower _B_ound _P_roof [5 marks]:  correct proof of lower bound.

    _U_pper _B_ound _S_ubstitution [3 marks]:  correct substitution (or use
        of Master Theorem) for upper bound.

    _U_pper _B_ound [2 marks]:  correct upper bound.

    _U_pper _B_ound _P_roof [5 marks]:  correct proof of upper bound.

    Marker's comments:

     -  Repeated substitution is not a proof of a bound.  You must prove
        bounds after you find likely candidates for them.

     -  Review complexity theory: n - log(n) is O(n).

     -  General issues with algebra.

     -  If you are unable to answer the question, outline how you would
        solve the question, leaving out the details



2.  [27 marks]

    Marker's comments:

     -  Make sure you understand what the problem is asking.  If  you don't
        understand what is meant by height balanced, ask someone.
        Same with part (d) -- most of the problems came from not
        understanding the question.

    (a) [6 marks]

        _S_tructure [1 marks]:  clear attempt to prove by universal
            generalization or by induction, with correct structure.

        _P_roof [5 marks]:  correct proof.

    (b) [8 marks]

        _S_tructure [1 marks]:  clear attempt to give an explicit
            recurrence (including base cases) and to explain it from the
            definition of s(h).

        _R_ecurrence [4 marks]:  correct recurrence (including base cases).

        _J_ustification [3 marks]:  good explanation of recurrence.

    (c) [8 marks]

        _S_tructure [3 marks]:  clear attempt to prove by induction, with
            correct inductive structure.

        _P_roof [5 marks]:  correct proof.

    (d) [5 marks]

        _S_tructure [1 marks]:  clear attempt to solve for h in some
            appropriate inequality involving h and n.

        _B_ound [4 marks]:  correct bound derived, and correct derivation.


3.  [27 marks]

    _S_tructure [9 marks]:  clear attempt to prove the correctness of each
        algorithm by induction on n, including correct induction structure.

    _P_roof _1_ [6 marks]:  correct proof for Fib1.

    _P_roof _2_ [6 marks]:  correct proof for Fib2.

    _P_roof _3_ [6 marks]:  correct proof for Fib3.

    Marker's comments:  By and large, very well done question.


BONUS

    (a) [12 marks]

        _B_ounds [6 marks]:  good bounds derived for T_1, T_2, T_3.

        _P_roofs [6 marks]:  correct proofs of bounds.

    (b) [4 marks]

        _C_omputation [4 marks]:  correct computation for T_1, T_2, T_3.