===========================================================================
CSC 165            Homework Exercise 5 -- Marking Scheme        Winter 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, so your marking should be somewhat coarse.  And
remember that marking is not only about evaluating a student's performance,
but also mostly about giving them feedback so that they can learn from
their mistakes.  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).  Your marking
comments will be included in this marking scheme and posted on the course
website so that students may look up the meaning of marking codes and
understand how their work was marked.


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

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

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


1.  [8 marks]

    _P_ proof [1 mark]:  clear attempt to prove the statement

    _S_ structure [4 marks]:  correct proof structure (assumptions, use of
        'let', conclusions, indentation, etc.)
        [independently of the correctness of the solution, i.e., give full
         marks for a correct structure to disprove the statement, or for a
         correctly structured proof using incorrect reasoning]

    _C_ correctness [3 marks]:  correct proof (values of c and B, argument
        that 4 n^3 - 2 n^2 >= c n^2, etc.)

    Marker's Comments / Error Codes:

    This question was very well done in general.  Be sure to specify
    *constant* values for c and B -- in particular, c cannot be a function
    of n, because then you can prove anything at all.  This also applies to
    question 2.


2.  [12 marks]

    _D_ disproof [1 mark]:  clear attempt to disprove the statement

    _S_ structure [6 marks]:  correct proof structure (assumptions, use of
        'let', conclusions, indentation, etc.)
        [independently of the correctness of the solution, i.e., give full
         marks for a correct structure to prove the statement, or for a
         correctly structured "disproof" using incorrect reasoning]

    _C_ correctness [5 marks]:  correct "disproof" (value of n, argument
        that 5 + 1/n < c n, justification that this disproves the
        statement, etc.)

    Marker's Comments / Error Codes:

    This question was also well done in general.  Just be careful when
    negating over quantifiers; remember that for any proposition P(x),
    \not \exists x, P(x) <==> \forall x \not P(x).

    Also, \not (a <= b <= c) <==> (a > b) \or (b > c) (notice the
    alternation between the non-strict and strict inequalities, and the
    additional \or, because of the implicit \and in the left hand side.)