CSC236 -- Fall 2007 -- Grading Scheme for Problem Set 1
-------------------------------------------------------

NOTE TO STUDENTS:

You will find below the marking scheme used in Problem Set 1, 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 problem set 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 problem set.


NOTE TO MARKER:

For each question, I list solution elements with associated codes (for
writing on student papers) and 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.  You will likely encounter
other common errors, e.g., writing the inductive hypothesis as "suppose for
all n" (which I would classify as incorrect use of notation), or a proof
where the inductive hypothesis does not connect with the base case(s)
(which should lose the mark(s) for hypothesis, and more if it cannot be
dismissed as a typographical error), etc.  Simply keep track of the most
common ones, 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).

Submission bonuses (+5%) or penalties (-10%) are to be computed as a
percentage of the grade obtained on the assignment, NOT as a percentage of
the total -- e.g., a grade of 34/40 with penalty of -10% gets a final mark
of 30.6 = 34 - 3.4.


General errors (marked negatively):

    N-  Notation: incorrect/ambiguous notation.  [up to 4]

    A-  Assumption: invalid implicit assumption.  [up to 4]

    U-  Unfounded: incorrect/unjustified/vague claim.  [up to 4]


1.  Solution elements:

        F-  Format: correct proof format (proof by contradiction,
            definition of set, argument set non-empty, use of well ordering
            to conclude existence of smallest element, reasoning about
            smallest element to get contradiction).  [2]

        S-  Set: correct definition of set.  [2]

        W-  Well ordering: correct application of well ordering
            (argument set non-empty, existence of smallest element).  [2]

        C-  Contradiction: correct proof of contradiction.  [4]

    Common errors:

        I-  Induction: mark inductive proofs according to the scheme
            outlined in question 2 below, then halve the mark (truncate to
            nearest 1/2 mark).

    Marker's comments:

     -  Common mistake: incorrect definition of the set.
        For any predicate P, ~ \-/ P <=> -] ~ P, ~ -] P <=> \-/ ~ P.


2.  Solution elements:

        F-  Format: correct proof format (definition of P(n), base case,
            inductive hypothesis, inductive step, conclusion).  [2]

        P-  Predicate: correct definition for predicate P(n).  [2]

        B-  Base case: correct proof of base case.  [1]

        H-  Hypothesis: correct inductive hypothesis.  [1]

        S-  Step: correct proof of inductive step.  [4]

    Common errors:

        D-  Direct proof: step does not make use of hypothesis.  [up to 2]

        E-  Equal: proof that number of even-sized subsets = number of
            odd-sized subsets, using induction  [8: as above except 3 for S
            and 1 for BH together -- -7 for making the claim without proof]

        R-  Reference: explicit use of fact from class (about total number
            of subsets) to conclude correct answer.  [2]

    Marker's comments:

     -  Be careful with the properties of powers, i.e., for a,b > 1,
        2^a + 2^b << 2^{a+b} ('<<' means 'is much smaller than').

     -  When you argue that there is a bijection, it would better if you
        define it and argue that is one-to-one and onto.


3.  2 marks for each part: 1 for the correct answer, 1 for a reasonable
    justification -- it's possible to get the justification mark for
    incorrect answers.

    Marker's comments:

     -  Pay attention when you are trying to find the base case, to be the
        minimum possible.


4.  See question 2 (except for codes E, R that do not apply).

    Marker's comments:

     -  Common mistake:  Applying induction on the number of walks without
        arguing about the walk and why it can be extended.  (Symbol (F) was
        used to mean that you didn't give a graphical argument about the
        walk, see next.)

     -  The walk guaranteed by the (IH) should end at a corner of the `big'
        triangle in order to extend it.