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

NOTE TO STUDENTS:

You will find below the marking scheme used in Problem Set 2, 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:

Be picky!  On problem sets and assignments, 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 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).


General errors (marked negatively, in addition to any other errors):

    _C_alculation [up to 10%]:  calculation error

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

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


1.  Solution elements:

    _I_dea [2 marks]:  "T exists because regular languages are closed under
        complementation"

    _D_etails [3 marks]:  citing relevant constructions to justify T's
        existence

    Marker's Comments:
        Showing examples doesn't prove!  It can just help you understand.
        Restating the question and the definition of complement over and
        over doesn't prove your claim.

    Codes for Common Errors:
        _RS_:  Restating the question without any actual proof at all.


2.  (a) [3 marks]  Solution elements:

    _F_SA [2 marks]:  correct FSA
     -  -0.5 if accepting state is misplaced, but only one exists
     -  -0.5 if start arrow of FSA is missing, without naming/numbering the
        states
     -  -0.25 if start arrow is missing, but states named/numbered

     *  same percentage of mark deduction applied for the same mistakes in
        other FSAs of this problem set

    _J_ustification [1 mark]:  reasonable argument of correctness
     -  you should explain one of these approaches: "remainder", "mod", or
        "the form of 3k+i; where i=0,1,2"
     -  explain what the meaning of each state is

    Marker's Comments:  (included with each solution element)


2.  (b) [1-4 marks]  Solution elements:

    _S_pecial case:  give 1 mark for solutions equivalent to "this is a
        special case of part (c)", and mark part (c) out of 11 instead

    _E_xhaustiveness [2 marks]:  argument covers all possible 2-state FSA

    _A_rgument [2 mark]:  correct argument in each case

    Marker's Comments:  FSA means DFA here.
    Common Mistake:  Mentioning one state must be accepting, and one state
    must be rejecting, without supporting the claim; explanation needed!


2.  (c) [8-11 marks]  Solution elements:

    _L_anguage [1 mark]:  correct language L
     -  -0.25 if "k >= 2" missing, but "k in N" mentioned
     -  -0.5 if both missing

    _R_egularity [1 mark]:  correct FSA for language
     -  expected drawing or full description of FSA

    _S_tructure [2 marks]:  attempt proof by contradiction, with correct
        outline

    _A_rgument [4-7 marks]:  correct proof

    Marker's Comments:
     -  pumping lemma is another approach of this question; but highly
        sensitive to mark deduction ;) as you have to be exact of details
        involved


3.  Solution elements:

    _S_tructure [3 marks]:  clear attempt to
     -  give FSA or RE and
     -  justify its correctness
     -  by describing "meaning" of each state

    _F_SA [3 marks]:  correct FSA or RE
     -  if more than 3 states in your FSA, some marks deducted based on
        severeness of the situation, e.g.:
        -1: if correct but more states than 3
        -3: if completely wrong
        -2: other situations in between (some states unreasonable)

    _J_ustification [4 marks]:  reasonable argument of correctness

    Note:  For answers where the FSA is not obviously correct and the
    justification is incomplete or inconclusive, it is reasonable to take
    off marks on the correctness of the FSA.

    Marker's Comments:  (included with each solution element)