===========================================================================
CSC 373           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.  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

General Marker's Comments:
 -  Many students seem to be under the impression that you can find maximum
    flow in /linear/ time -- max flow algorithms take time O(n^3).
 -  Some students are under the impression that you can solve integer
    programs in polytime using simplex -- general integer programs are
    NP-hard and require exponential time to solve, and the simplex
    algorithm is *not* a worst-case polytime algorithm!


1.  [15 marks]:  any properly structured attempt should earn at least 3

    _A_lgorithm [5 marks]:  clear and correct polytime algorithm

    _C_orrectness [8 marks]:  clear and complete argument that algorithm
        is correct

    _R_untime [2 marks]:  clear and correct runtime analysis


2.  [26 marks]:  any properly structured attempt should earn at least 6

    (a) [8 marks]:  any properly structured attempt should earn at least 2

        _N_etwork [2 marks]:  clear and correct network construction

        _A_lgorithm [2 mark]:  clear and correct construction of schedule

        _C_orrectness [3 marks]:  clear and complete argument that algorithm
            is correct

        _R_untime [1 mark]:  clear and correct runtime analysis

    (b) [8 marks]:  any properly structured attempt should earn at least 2

        For each part:

        _A_nswer [1 mark for each part]:  clear and correct answer

        _J_ustification [1 mark for each part]:  good and complete
            justification

        Keep in mind that the network could have been constructed in the
        reverse direction from the sample solutions -- this affects the
        answers.

    (c) [10 marks]:  any properly structured attempt should earn at least 2

        _N_etwork [4 marks]:  clear and correct network construction

        _A_lgorithm [1 mark]:  clear and correct construction of schedule

        _C_orrectness [4 marks]:  clear and complete argument that
            algorithm is correct

        _R_untime [1 mark]:  clear and correct runtime analysis


3.  [12 marks]:  any properly structured attempt should earn at least 2

    _A_lgorithm [6 marks]:  clear and correct algorithm to find actors and
        investors that maximize profit

    _C_orrectness [6 marks]:  clear and complete argument that algorithm
        is correct

    For students who attempted to solve this through a network flow
    algorithm (it was possible to do this), marks are allocated as follows:

    _N_etwork [4 marks]:  clear and correct network construction

    _A_lgorithm [2 marks]:  clear and correct algorithm to find actors and
        investors based on the network

    _C_orrectness [6 marks]:  clear and complete argument that algorithm
        is correct


4.  [12 marks]:  any properly structured attempt should earn at least 2

    _LP_ [3 marks]:  clear and correct LP representation of problem
        (variables, objective function, and constraints)

    _J_ustification [6 marks]:  clear and complete justification that
        LP/algorithm is correct

    _S_olution [3 marks]:  clear and correct description of how to
        reconstruct an optimal solution


5.  [15 marks]:  any properly structured attempt should earn at least 3

    _D_efinition [3 marks]:  clear and correct application of definition of
        "approximation ratio"

    _L_emma [6 marks]:  clear and correct proof of lemma from hint

    _P_roof [6 marks]:  clear and correct proof of approximation ratio