===========================================================================
CSC 363            Homework Exercise 6 -- Marking Scheme          Fall 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.
And remember that marking is not just about evaluating the students's
performances, but also 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).


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

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

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


1.  [15 marks]

    _S_tructure [3 marks]:  clear attempt to show X4SAT (- NP by describing
        a polytime verifier for X4SAT (including appropriate structure of
        the verifier), then to show X4SAT is NP-hard by proving A <=p X4SAT
        for some NP-hard A (including correct structure: start with
        arbitrary input x for A, construct specific input F_x for X4SAT,
        argue construction takes polytime and x (- A iff F_x (- X4SAT)

    _NP_ [2 marks]:  correct polytime verifier for X4SAT

    _R_eduction [5 marks]:  correct reduction function:
        [1 mark]:  polytime,
        [2 marks]:  x (- A implies F_x (- X4SAT, and
        [2 marks]:  F_x (- X4SAT implies x (- A

    _P_olytime [1 mark]:  statement that reduction is polytime computable

    _C_orrectness [4 marks]:  good argument that reduction is correct
        (2 marks for each direction)

    Note to Marker:  Students were given a detailed write-up of the
        reduction CNF-SAT <=p 3SAT as a template.

    Expected Errors:

    _T_emplate:  student simply modified the reduction from CNF-SAT to
        construct a formula in 4-CNF, but forgot to ensure the formula is
        in exact 4-CNF (with no repeated variables inside any clause)
        [-4 marks for _R_eduction and -4 marks for _C_orrectness, at least]

    _X_4SAT:  student attempted to construct a formula in exact 4-CNF but
        failed (formula may contain repeated variables)
        [-2 marks for _R_eduction and -2 marks for _C_orrectness, at least]

    Marker's Comments/Error Codes:

    E1:  Why is the input a well-formed propositional formula?

    E2:  Proof of correctness of the reduction?  (I.e., where is a clear
        justification that the construction/algorithm is indeed a valid
        reduction?)

    E3:  Why is the construction polytime?

    E4:  Use of repeated literals to "pad" the clauses.

    E5:  Inverse direction!  X4SAT <=p SAT was known and in particular does
        NOT prove that X4SAT is NP-complete.

     -  I did not subtract marks when they didn't check well-formedness
        in the reduction.

     -  Common major mistake: the clause is padded using new variables such
        that it is always true.  This is a major mistake in the reduction
        (i.e., the reduction does not work).  Based on the marking scheme I
        did not award more than 6 marks for such an answer.