CSC236 -- Fall 2007 -- Grading Scheme for Problem Set 2 ------------------------------------------------------- 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: _R_ecurrence [2 marks]: correct recurrence, including base case (exact values of constants don't matter, as long as they are justified) 1 for a base case 1 for a recursive case _J_ustification [3 marks]: values of constants in recurrence are justified from algorithm; size of inputs for recursive calls are computed correctly 1 for justifying the constants in the recurrence 2 for calculating the size of inputs to recursive calls Marker's Comments: (none) 2. Solution elements: _E_xpression [4 marks]: correct closed-form for T(n), including method used to obtain the expression (based on Question 1, i.e., give full marks for answer consistent with recurrence, even if recurrence was incorrect) 2 for writing down a closed-form solution 2 for work showing method used to derive expression _F_ormat [2 marks]: correct inductive proof format, including correct statement of inductive hypothesis (independently of correctness of proof itself) 1 for correct statement of inductive hypothesis 1 for having correct format (base case, IH, inductive step) _I_nduction [4 marks]: correct proof of base case and inductive step, including appropriate use of inductive hypothesis 1 for proof of base case 2 for appropriate use of IH (and justification of use) 1 for proof of inductive step Marker's Comments: - Many, many people used strong induction but did NOT include "n is a power of 3" in their inductive hypotheses. 3. Solution elements: _P_re/post-conditions [4 marks]: reasonable pre- and post-conditions (take marks off for unnecessary preconditions, e.g., "A is sorted") preconditions: 1/2 for "A is a nonempty list" 1 for 1 <= b <= e <= length(A) 1/2 for "x is comparable with elements of A[b...e]" 1/2 for no superfluous preconditions postcondition: 1/2 for realizing that Mystery returns the NUMBER of elements < x 1 for realizing that it only counts elements in A[b...e] _F_ormat [3 marks]: correct format for proof of correctness (prove postcondition holds for all inputs that satisfy precondition, by induction on input size), including correct statement of inductive hypothesis 2 for correct general format (proving pre+execution-->post by induction on input size, with all the right pieces: base case, IH, inductive step) 1 for correct statement of IH _I_nduction [5 marks]: correct proof of base case and inductive step, including appropriate use of inductive hypothesis and justification that it applies (that preconditions are met for recursive calls) 1 for proof of base case 1 for correct proof of inductive step 1 for appropriate use of IH 2 for justifying use of IH correctly Marker's Comments: - Only two people correctly required the precondition that "A is a nonempty list." - It was popular to require that A was sorted, or that its elements were comparable to each other. Both were unnecessary preconditions. - I didn't deduct points, but many people included "n is a power of 3" in their preconditions. - Although everyone was proving something different (since no two people picked an identical set of preconditions), proofs by induction for problem 3 had the right general idea (many people explicitly said, "the inductive proof follows the recursive algorithm in structure," which was a good sign!) but executed it poorly. Almost no one fully justified their invocation of the inductive hypothesis (failing to show that preconditions were satisfied for the smaller cases (recursive calls)). - Another common mistake was to simply invoke the IH and then conclude the postcondition, without explaining how the postconditions for the recursive calls imply the postcondition overall. 4. Solution elements: _A_nswer [1 mark]: correct answer ("no") 1 for "no" _J_ustification [2 marks]: correct counter-example, including demonstration that algorithm fails (i.e., not enough to just say "algorithm doesn't work on this input"; students must explain why it fails) 1 for a counter-example that works 1 for explaining WHY and HOW the counter-example fails Marker's Comments: - Many, many people used strong induction but did NOT include "n is a power of 3" in their inductive hypotheses. - A common mistake was to give a conterexample (e.g., n=2) and then say that it violates the precondition, so the postcondition must not hold. This is not true! In terms of logic, (pre)-->(post) does NOT imply the logical inverse, i.e., (not pre)-->(not post). (If a student said this but still went on to explain how this causes an infinite loop, I gave full credit.)