===========================================================================
CSC 373            Homework Exercise 4 -- 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 give an explicit divide and
        conquer algorithm written in pseudo-code, to explain/justify its
        correctness and analyze its runtime, and to prove the inequality
        given in the question about C(n)

    _A_lgorithm [5 marks]:  algorithm correctly finds three smallest
        elements in order, and has correct runtime

    _R_untime [2 marks]:  algorithm's runtime is correctly analyzed to show
        it satisfies recurrence from question

    _P_roof [5 marks]:  correct proof that C(n) <= 2n - 3 for all n >= 3

    Marker's Comments:

    Reasonably well done.  Most people got this, although many forgot about
    certain cases.  Also, some had trouble writing up a correct induction
    proof, e.g., their "inductive step" didn't even make use of the
    induction hypothesis.


2.  [6 BONUS marks]

    Be *especially* picky for this one, as it is a bonus!

    _S4_ [3 marks]:  correct algorithm for solve_four(), with correct
        runtime and good justification of correctness

    _S5_ [3 marks]:  correct algorithm for solve_five(), with correct
        runtime and good justification of correctness

    Marker's Comments:

    As instructed, I was harsher for this question.  In particular, while I
    didn't count comparisons incurred by while or for loops in the main
    question, I counted them here.

    Many people tried this but few got it right.  There is a simple
    recursive solution, making one call to solve_{n-1} inside solve_{n},
    found by almost nobody.  Most people wanted to do it using only
    comparisons, which was more difficult and harder to justify correct.