CSC236 -- Fall 2007 -- Grading Scheme for Assignment 2
------------------------------------------------------

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 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 keep track 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) -- make sure you
keep a list of any new codes you use, their meaning, and the associated
number of marks, so that we can make this information available.

Be picky!  Students are responsible for showing that they understand and
for writing up their answers clearly and precisely.  Keep in mind that
they've had the time to ask questions, to formulate their answers, and to
write them up.  Also keep in mind the Faculty's guidelines for the meaning
of grades:
 A- [80-100]  Exceptional performance:
    strong evidence of original thinking; good organization, capacity to
    analyze and synthesize; superior grasp of subject matter with sound
    critical evaluations; evidence of extensive knowledge base.
 B- [70-80]  Good performance:
    evidence of grasp of subject matter; some evidence of critical capacity
    and analytic ability; reasonable understanding of relevant issues;
    evidence of familiarity with the literature.
 C- [60-70]  Intellectually adequate performance:
    student who is profiting from her or his university experience;
    understanding of the subject matter and ability to develop solutions to
    simple problems in the material.
 D- [50-60]  Minimally acceptable performance:
    some evidence of familiarity with subject matter and some evidence that
    critical and analytic skills have been developed.
 F- [0-50]  Inadequate performance:
    little evidence of even superficial understanding of the subject
    matter; weakness in critical and analytic skills; with limited or
    irrelevant use of literature.


General errors (marked negatively):

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

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

General marker's comments:

 -  The comments below contain the shorthands used for the common errors.
    All other ones were noted on the assignment paper itself.

 -  The grades pointed out below have been taken off for a mistake in the
    common case.  The penalty in some individual cases could have been less
    or greater, depending on the severity of the error, and how many
    related errors were caused.

 -  Many simple errors listed below actually led to bigger mistakes in
    proofs.  For example, assuming that 'a - b' is a natural number if both
    a and b are natural numbers in most cases defeated the purpose of proof
    of termination and lead to a trivial proof for a non-trivial (and
    sometimes wrong) algorithm.

 -  When you are writing out a step in the proof, ask yourself: what is
    this step supposed to accomplish?  What kind of errors in the algorithm
    does this guard me against?  Thinking about and understanding such
    things would help avoid such errors.


1.  Solution elements:

    _S_tructure [2 marks]:  Clear attempt to define expression E and show
        that for all k in N, E_k in N and E_{k+1} < E_k (if there is an
        iteration number k+1), then use well ordering to conclude
        termination.  Clear and correct use of induction on the number of
        iterations to prove loop invariant.

    _I_nvariant [2 marks]:  Correct loop invariant and proof of invariance.

    _T_ermination [1 mark]:  Correct proof of properties of E that imply
        termination, based on loop invariant.

    Note:  There are many elements to get right for the small number of
    marks, so don't hesitate to give .5 marks when appropriate.

    Marker's codes and comments:

    Y0, X0: Requiring that initially y!=0 or x!=0: this is too strong and
            unnecessary. [0.5]
    XN:     Failing to prove that x is a natural number. [0.5 if it was
            not adequately proven, 1 if it was not mentioned]
    FE:     Stating a loop invariant that is false on exit (for example,
            y!=0). [0.5]
    WOP:    Failing to adequately use Well Ordering Principle. [1]
    BC:     Induction for k>0 without proving the loop invariant holds
            initially. [0.5]


2.  Solution elements:

    _I_nvariant [1 mark]:  Clear and correct loop invariant.

    _P_rogram [3 marks]:  Clear and correct code for the loop condition,
        loop body, and following the loop.

    _C_orrectness [4 marks]:  Clear explanation of how code preserves
        invariant (no formal proof required; using pictures is fine),
        and argument that postcondition is satisfied.

    _T_ermination [2 marks]:  Clear and correct argument that loop
        terminates (no formal proof required).

    Marker's codes and comments:

    LE:     Confusing '<=x' and '<x'. [0.5-1, depending on severity]
    RA:     Loop Invariant does not include the condition that the values
            are in range of the array. [0.5]
    FE:     Stating a loop invariant that is false on exit (for example,
            b < e). [0.5]
    EQ:     Including a special case to return m if A[m]==x.  What if the
            array contains only values x?  This does not satisfy the
            postcondition that is stated in the question. [1]
    POST:   Postcondition is not adequately proven [1] or is completely
            left out. [2]
    ST:     Setting b=m: then the loop might never terminate if e=b+1.
            [0.5]
    EM:     Setting e=m-1: this might violate the loop invariant. [0.5]
    PB:     Forgetting to set p=b, or to identify the return value. [0.5]


3.  Solution elements:

    _S_tructure [4 marks]:  Correct high-level structure for correctness of
        recursive algorithm (prove that postcondition holds for all inputs
        that meet preconditions, by induction on size of input); correct
        structure for partial correctness and termination of loops (prove
        loop invariant by induction on number of iterations, prove
        termination by well ordering); appropriate (and correct) use of
        induction in both cases.

    _I_nvariants [3 marks]:  Correct loop invariants for all loops.

    _L_oops [4 marks]:  Correct arguments of partial correctness and
        termination, for all loops.

    _R_ecursion [4 marks]:  Correct argument of recursive correctness.

    Marker's codes and comments:

    MC:     Missed Cases: when proving correctness, some important cases
            were left out. [depends on which cases were missed]
    WL:     Weak loop invariant. [depends on how weak]
    IP:     It is not proven that the postcondition of the recursive call
            implies the current postcondition. [1]
    SP:     It is not proven that the input size of the recursive call is
            smaller than the current. [1]
    Pre:    If is not proven that the preconditions of the recursive call
            hold. [1]
    NN:     Assuming that a-b is a natural number if both a and b are
            natural numbers. [1]


4.  Solution elements:  (same for each part; justification worth 2/4)

    _R_egexp [2 marks]:  Correct reg. exp. and justification.

    _F_SA [2 marks]:  Correct FSA and justification.

    Marker's codes and comments:

    WE:     Weak explanation; doesn't tell much beyond restating the
            FSA/RE.  [0.5-1]

     -  Errors on RE or FSA were weighted [0.5-1], depending on the
        severity.  Often, a more thorough explanation could have helped
        avoid those errors.  In those cases, the explanations were also
        penalized.  In some cases, the explanation was thorough enough, but
        missed a small subcase.  In that case, only the RE/FSA was
        penalized.

     -  Some people attempted to convert the DFA into a regular expression
        mechanically.  This is a long and tedius process, and nobody was
        able to do this correctly.  The most common error was forgetting
        that all the final states have to be treated separately, and the
        resulting expressions combined.  A better approach is to reason
        about the language and to write out the expression from scratch.


5.  Solution elements:

    _S_tructure [1 mark]:  Clear attempt to reason about arbitrary finite
        language and describe specific regular expression for it.

    _C_orrectness [2 marks]:  Correct high-level argument.

    Marker's codes and comments:

    LL:     The proof did not justify that L=L(R). [0.5]
    RE:     The proof only claimed that R (or a part of R) exists, without
            specifying it, or showing how it can be obtained. [0.5]

     -  There was some confusion about terminology, especially evident in
        this question.  An ALPHABET is a set of characters.  A SYMBOL is a
        single character.  A LANGUAGE can never BE a string.  Even if it
        contains a string, it is still a SET of strings (perhaps containing
        a single element).

     -  As stated on the bulleting board, proving that L(s)={s} for a
        string s, was unnecessary.  No marks were taken off or awarded for
        this.

     -  In order to prove that L can be represented by a regular expression
        R, you cannot start with "Let L be a language that is represented
        by a regualr expression"!  This leads to a tautology.

     -  For some reason, some students only proved that it was possible to
        represent any single string as a regular expression.  This is not
        what the question asks for.  A language is a SET of strings.