===========================================================================
CSC 165            Homework Exercise 6 -- 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.  [20 marks]

    _L_ loop invariant [5 marks]:  clear attempt to prove that the loop
        invariant holds before the loop starts, and at the end of any
        iteration for which it held at the beginning (even if the proofs
        themselves are incorrect)

    _S_ structure [5 marks]:  clear and correct proof structures (even if
        the content is missing or incorrect)

    _H_ high-level [5 marks]:  correct high-level idea of the proof

    _D_ details [5 marks]:  correct details in the proof

    Marker's Comments / Error Codes:

    A surprising number did not include the base case, i.e., did not show
    that the loop invariant was true before the execution of the loop.

    More explicit reference to the code would have been desirable in many
    cases, by stating in sentences the connection to code (or citing a line
    number/Python statement).  Marks were only deducted for steps that were
    completely unjustified (even if correct).

    The most common unjustified step was whimsically asserting that i_k + 1
    <= len(A) without giving any reason.  The reason is that i_k < len(A)
    (NOTE: STRICTLY less than, stronger than the loop invariant because of
    the loop condition -- if i_k >= len(A) we would have not entered this
    iteration of the loop!).  Some went as far as to suggest that a <= b
    implies a + 1 <= b, a serious arithmetic error, and were penalized more
    harshly.

    Listed below are codes for various common deductions.  They do not
    cover all deductions, more detailed markup can be found on your marked
    assignment.

    Loop invariant:

    _B_ Base case missing entirely (did not consider loop invariant before
        any execution takes place).  [-2]

    _Y_ Not an inductive proof; covers a single iteration from i = 0,
        doesn't convey an understanding of induction.  [-3]

    High-level deductions:

    _Z_ Incorrect format.  Informal description/justification of the
        algorithm, rather than a loop invariant proof.  [-4]

    Details deductions:

    _T_ Symbolic statement given but is has serious problems.  [-2]

    _Q_ Omitted all mention of the loop condition (as opposed to loop
        invariant), failed to justify why i_k + 1 <= len(A) (i < len(A) in
        loop condition, i and len(A) are integer, thus i + 1 <= len(A)).
        [-1]

    _I_ Trouble with inequalities, < vs. <=, etc.  For example, x <= y does
        *NOT* imply x + 1 <= y.  [-2]

    _R_ Doesn't cover the "return" case, or incorrectly recognizes it as a
        contradiction.  Fails to show loop invariant holds in this case.
        [-2]

    _C_ Unnecessary cases that don't cover the problem adequately, omission
        of cases, confusion about what cases are necessary.  [-1]

    Miscellaneous deductions:

    _P_ Imprecise or false statements (noted/circled on paper).
        [-1 or -2 depending on severity]