===========================================================================
CSC 236           Homework Assignment 3 -- 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.  [36 marks]

    Each group's solution was unique, so many of the marks for proofs
    (below) were awarded on a subjective basis.  Where marks were deducted,
    accompanying comments on your assignment should explain why.

    _S_tructure [6 marks]:  clear attempt to prove the correctness of the
        entire algorithm by proving partial correctness and termination;
        clear attempt to fill in LI^3 and LI^4 and to prove each loop
        invariant by induction on the number of iterations of the loop, in
        the right order (inside-out), with correct inductive structures.

        _In_duction: Proving the loop invariants by induction (NOT
            directly!).  One mark per loop invariant.

        _Or_der: It was possible to lose 1/2 mark for proving the loop
            invariants out-of-order (the proof of LI^2 required that
            LI^3 and LI^4 already be proven).

    _LI^1_ [4 marks]:  correct proof of invariant.

    _LI^2_ [6 marks]:  correct proof of invariant.

    _LI^3_ [6 marks]:  correct loop invariant (2 marks) and proof (4
        marks). A correct proof of a nearly-correct loop invariant
        merited the four marks for proof.  An incorrect proof, or a
        proof of a false loop invariant, merited zero marks.

    _LI^4_ [6 marks]:  correct loop invariant (2 marks) and proof (4
        marks). Partial credit as for LI^3 above.

    _T_ermination [4 marks]:  correct proof of termination.

    _P_artial _C_orrectness [4 marks]:  correct proof of partial
        correctness.


2.  [20 marks]

    _S_tructure [4 marks]:  clear attempt to give an explicit NFA and an
        explicit DFA and to explain why they are correct (see below for
        what constitutes a reasonable explanation and give marks for
        attempting this).

        This breaks down into:
         -  explicit NFA (1 mark)
         -  explicit DFA (1 mark)
         -  explanation why NFA is correct (1 mark)
         -  explanation why DFA is correct (1 mark)

    _NFA_ [4 marks]:  correct NFA.

    _N_J_ustification [4 marks]:  good justification of NFA's correctness
        (steps of construction from RE, or explanation).  It was
        possible to lose one mark here for pulling a RE out of thin
        air, with no reason/explanation/motivation.

    _DFA_ [4 marks]: correct DFA.

    _D_J_ustification [4 marks]:  good justification of DFA's correctness
        (steps of construction, or statement about properties of strings
        that end up at each state).


3.  [24 marks]

    _S_tructure [6 marks]:  clear attempt to give a FSA and RE, to prove
        the correctness of the FSA by giving an explicit statement about
        the properties of strings that end up at each state and proving
        this by induction (including correct format for the induction), and
        to show the steps in the construction of the RE from the FSA.

        This breaks down into the presence of the following:
         -  FSA (1 mark)
         -  RE (1 mark)
         -  attempted proof of correctness of FSA (1 mark -- code _N_)
         -  proving statement by induction (2 marks -- code _I_)
         -  steps of construction of RE (1 mark -- code _T_)

    _FSA_ [4 marks]: correct FSA.  (For each node, remember to include
        one, and only one, transition for each character in the
        alphabet -- many groups forgot to include self-loops!)

    _P_roof [8 marks]:  correct proof of correctness for FSA.

    _RE_ [2 marks]:  correct RE -- mark as correct if construction is
        carried out correctly, even if starting from an incorrect FSA.

    _C_onstruction [4 marks]:  correct construction of RE.

    (If RE was obtained "directly", rather than through construction, give
    3 marks each for the FSA and RE, and 6 marks each for the proofs of
    correctness.)