===========================================================================
CSC 236            Homework Exercise 5 -- 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.  At the same time, keep in mind that exercises are worth
only 1.5% of the final grade, so your marking should be somewhat coarse.

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

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

Marker's comment:

    _R_epeated solution:  there is a one point penalty (possible on
        problems 2, 3, and 4) for repeating an identical solution, e.g.,
        offering the three "different" languages {a}, {b}, and {c}, which
        is really three times the same language.

1.  [3 marks]

    _S_tructure [1 mark]:  clear, well written attempt to list the
        language and provide an explicit predicate to describe the strings
        in the language.

    _L_ist [1 mark]:  correct list of {a,ab}*.

    _P_redicate [1 mark]:  correct predicate P(s).  (A proof was not
        required, but kudos to those who gave one!)  This was picky -- the
        assignment specified "a clear, concise way to describe strings in
        this language," so *technically* correct, but unclear, predicates
        earned zero marks.


2.  [4 marks]

    _S_tructure [1 mark]:  clear, well written attempt to give three
        explicit, different languages L with the property that L = L.L, and
        to provide a justification for each language.

    _L_anguages [2 marks]: correct languages.  Offering one correct,
        and two incorrect, languages costs both marks.

    _J_ustifications [1 mark]:  good justifications.


3.  [4 marks]

    _S_tructure [1 mark]:  clear, well written attempt to give three
        explicit, different languages L with the property that L = L.L, and
        to provide a justification for each language.

    _L_anguages [2 marks]: correct languages.  Offering one correct,
        and two incorrect, languages costs both marks.

    _J_ustifications [1 mark]:  good justifications.


4.  [4 marks]

    _S_tructure [1 mark]:  clear, well written attempt to give three
        explicit, different pairs of languages L_1, L_2 with the property
        that L_1.L_2 = L_2.L_1, and to provide a justification for each
        pair of languages.

    _L_anguages [2 marks]: correct pairs of languages.  Offering one
        correct, and two incorrect, pairs of languages costs both
        marks.

    _J_ustifications [1 mark]:  good justifications.

    Marker's comments:

    The code _N_ (with a possible 1 point penalty) indicates that you gave
    an answer with L_1 = L_2 (the temptation seems to be recycling answers
    from problem 2, although some N penalties didn't even go that far).