===========================================================================
CSC 363           Homework Assignment 3 -- 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.  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

General Marker's Comments/Error Codes:

    I have included a PDF with common counter-examples.

    E1:  Give a clear, explicit argument that CNC (- DP.

    E2:  The argument cannot rely on DP = NP u coNP.

    E3:  See PDF Example 1 for question 3 (consider a 6-cycle).

    E4:  Where is the argument for hardness?

    E5:  See PDF Example 2 for question 1 (linear arrangement).

    E6:  See PDF Example 3 for question 1 (only 2 vars).

    E7:  See PDF Example 4 for question 3.

    E8:  See PDF Example 5 for question 1.

    General remark:  We don't know whether there are NP-complete problems
        not in P.

    Minor remark:  There is not only polynomial and exponential running
        time.  For instance, how about n^{log n}?


1.  [15 marks]

    _NP_ [2 marks]:  clear and correct polytime verifier for CS

    _R_eduction [7 marks]:  clear and correct reduction 3SAT <=p CS:
        _S_tructure [2 marks]:  clear and correct structure of a reduction
            (even if idea is incorrect), i.e., attempt to construct
            specific inputs for CS from arbitrary inputs for 3SAT so that
            solutions are preserved
        _P_olytime [1 mark]:  reduction is polytime computable (even if not
            explicitly stated)
        _F_orward correctness [2 marks]:  reduction works in "forward"
            direction (if <F> (- 3SAT, then f(<F>) (- CS)
        _B_ackward correctness [2 marks]:  reduction works in "backward"
            direction (if f(<F>) (- CS, then <F> (- 3SAT)

    _C_orrectness [6 marks]:  clear and complete argument of correctness:
        _S_tructure [1 marks]:  both directions of the argument are present
            (even if ideas are incorrect)
        _P_olytime [1 mark]:  reduction is claimed to be polytime
            computable (even if claim is false)
        _F_orward correctness [2 marks]:  good argument for "forward"
            direction (if <F> (- 3SAT, then f(<F>) (- CS)
        _B_ackward correctness [2 marks]:  good argument for "forward"
            direction (if f(<F>) (- CS, then <F> (- 3SAT)


2.  [15 marks]

    (a) [15 marks]

        _DP_ [6 marks]:  clear and correct argument that CNC (- DP:
            _S_tructure [1 mark]:  attempt to give specific languages A, B
                in NP and show CNC = A - B (even if languages incorrect)
            _L_anguages [3 marks]:  correct languages A, B (- NP (even if
                correctness is not argued)
            _A_rgumant [2 marks]:  correct argument CNC = A - B (if not
                obvious)

        _H_ardness [9 marks]:  clear and correct argument that CNC is
            DP-hard:
            _S_tructure [2 marks]:  attempt to argue that A <=p CNC for all
                A (- DP (even if attempt fails)
            _R_eduction [4 marks]:  correct reduction A <=p CNC (structure,
                is polytime, works in both directions)
            _C_orrectness [3 marks]:  good argument that reduction is
                correct (polytime and works in both directions)

        Expected Errors:

        _CL_IQUE [-3 marks for _DP_]:  unsupported claim that
            CNC = CLIQUE - ~CLIQUE

        _M_isunderstanding [-5 marks for _H_]:  argument relies (implicitly
            or explicitly) on DP = NP n coNP (which is false)

    (b) [10 BONUS marks]

        Even though this is a bonus, please don't be too picky -- give part
        marks for reasonable attempts at a solution (just not too many).
        After all, I didn't realize how tricky this question was early
        enough to let students know before the submission deadline, and I
        want to give them a chance to get a few marks for the work that
        they put into it (as long as it's reasonable -- meaning they're
        trying to do the right things, even if they can't quite come up
        with the right idea).

        _DP_ [3 marks]:  clear and correct argument that MC (- DP

        _H_ardness [7 marks]:  clear and correct argument that MC is
            DP-hard


3.  [20 marks]

    _S_tructure [4 marks]:  clear attempt to give explicit algorithm to
        solve search problem by making calls to solver for decision
        problem, to argue that the algorithm is correct, and to show that
        its runtime is polynomial (as a function of the decision problem
        solver's runtime) -- give these marks even if the ideas are
        incorrect

    _A_lgorithm [8 marks]:  algorithm is correct and runs within the
        required time bound -- give these marks as long as the idea is
        clearly correct, even if the argument of correctnes and runtime
        analysis are missing, and give part marks for algorithms that are
        "close"

    _C_orrectness [6 marks]:  good argument that algorithm is correct

    _R_untime [2 marks]:  correct analysis of algorithm's runtime, as a
        function of runtime of decision problem solver


4.  [30 marks]

    For each part, give part marks for structure if the students try to
    show that the language belongs to the wrong class, but they go about it
    in the right way for the class they have selected.

    (a) [9 marks]

        _coNP_ [2 marks]:  clear and correct polytime verifier for ~SumGap

        _R_eduction [4 marks]:  clear and correct reduction:
            _S_tructure [1 marks]:  clear and correct structure of a
                polytime reduction (even if idea is incorrect)
            _P_olytime [1 mark]:  reduction is polytime computable (even if
                not explicitly stated)
            _F_orward correctness [1 mark]:  reduction works in "forward"
                direction
            _B_ackward correctness [1 mark]:  reduction works in "backward"
                direction

        _C_orrectness [3 marks]:  clear and complete argument of correctness:
            _S_tructure [1 marks]:  both directions of the argument are
                present (even if ideas are incorrect) and reduction is
                claimed to be polytime computable
            _F_orward correctness [1 mark]:  good argument for "forward"
                direction
            _B_ackward correctness [1 mark]:  good argument for "forward"
                direction

    (b) [4 marks]

        _A_lgorithm [3 marks]:  clear and correct polytime algorithm for
            NoLargeSum

        _J_ustification [1 mark]:  clear justification that algorithm is
            correct and runs in polytime

    (c) [8 marks]

        _NP_ [1 mark]:  clear and correct polytime verifier for EasySAT

        _R_eduction [4 marks]:  clear and correct reduction:
            _S_tructure [1 marks]:  clear and correct structure of a
                polytime reduction (even if idea is incorrect)
            _P_olytime [1 mark]:  reduction is polytime computable (even if
                not explicitly stated)
            _F_orward correctness [1 mark]:  reduction works in "forward"
                direction
            _B_ackward correctness [1 mark]:  reduction works in "backward"
                direction

        _C_orrectness [3 marks]:  clear and complete argument of correctness:
            _S_tructure [1 marks]:  both directions of the argument are
                present (even if ideas are incorrect) and reduction is
                claimed to be polytime computable
            _F_orward correctness [1 mark]:  good argument for "forward"
                direction
            _B_ackward correctness [1 mark]:  good argument for "forward"
                direction

    (d) [9 marks]

        _coNP_ [2 marks]:  clear and correct polytime verifier for
            ~NoLargeCycles

        _R_eduction [4 marks]:  clear and correct reduction:
            _S_tructure [1 marks]:  clear and correct structure of a
                polytime reduction (even if idea is incorrect)
            _P_olytime [1 mark]:  reduction is polytime computable (even if
                not explicitly stated)
            _F_orward correctness [1 mark]:  reduction works in "forward"
                direction
            _B_ackward correctness [1 mark]:  reduction works in "backward"
                direction

        _C_orrectness [3 marks]:  clear and complete argument of correctness:
            _S_tructure [1 marks]:  both directions of the argument are
                present (even if ideas are incorrect) and reduction is
                claimed to be polytime computable
            _F_orward correctness [1 mark]:  good argument for "forward"
                direction
            _B_ackward correctness [1 mark]:  good argument for "forward"
                direction