=========================================================================== CSC 236 Homework Exercise 1 -- Marking Scheme Winter 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. 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): _A_rithmetic/_A_lgebra [up to 10%]: calculation error _N_otation [up to 20%]: incorrect/ambiguous notation _V_agueness [up to 20%]: incorrect/unjustified/vague claim General marker's comments: - If no mark is explicitly given for a particular category, you got all marks for that category. - Please use an official cover sheet (from the course website). - Please STAPLE your work (no paper clips, folding, etc.) - Write down your student number on the work you submit. 1. [8 marks] Solution elements: _C_onjecture [1 mark]: correct conjecture -- mark the rest of the proof independently of the correctness of the conjecture (though it's likely to affect the correctness of either the base case or the inductive step). _F_ormat [2 mark]: correct proof structure (definition of predicate, base case, inductive hypothesis, inductive step, conclusion), independently of proof correctness. _P_redicate [1 mark]: correct definition for predicate P(n). _B_ase case [1 mark]: correct proof of base case. _H_ypothesis [1 mark]: correct inductive hypothesis. _S_tep [2 marks]: correct proof of inductive step. Expected errors: _D_irect proof [-1 mark]: step does not make use of hypothesis. Marker's comments: - Code (P/V): Stating something like "P(n) = \sum_{i=0}^{n} 2^{i+1}" is incorrect (or some variant of this used anywhere in the proof). Using P(n) anywhere in an algebraic expression is also incorrect, e.g., ``P(n) + 2^{n+2} = ...'' P(n) is supposed to be a *predicate*, i.e., for a given value of n it will take on a value of either true or false. This is clearly not the case for how P(n) is used above. - Code (V): Always justify statements. Whenever you conclude something in the IS due to the IH, say "by the IH" to make it clear where you used the IH. - Code (C): State your conjecture precisely. For example, simply writing "2^{n+2}-2" as your conjecture is incorrect. Also don't confuse your conjecture with your predicate -- you must say "*\-/ n (- N*, \sum_{i=0}^{n} 2^{i+1} = 2^{n+2}-2" (omitting the "\-/ n (- N" part gives you a predicate dependent on n, not a conjecture). Make sure you read the question correctly: at least one person copied the question incorrectly and tried proving something different. 2. [7 marks] Solution elements: _C_onjecture [1 mark]: correct conjecture -- mark the rest of the proof independently of the correctness of the conjecture (though it's likely to affect the correctness of either the base case or the inductive step). _F_ormat [1 mark]: correct proof structure (definition of predicate, base case, inductive hypothesis, inductive step, conclusion), independently of proof correctness. _P_redicate [1 mark]: correct definition for predicate P(n). _B_ase case [1 mark]: correct proof of base case. _H_ypothesis [1 mark]: correct inductive hypothesis. _S_tep [2 marks]: correct proof of inductive step. Expected errors: _D_irect proof [-1 mark]: step does not make use of hypothesis. Marker's comments: - Code (V): Always justify statements. Whenever you conclude something in the IS due to the IH, say "by the IH" to make it clear where you used the IH. - Code (I): Make sure the work you do in the base case and the induction step is consistent with how you defined your predicate. Proofs are slightly different for P(n): "-] a,b (- N, 3a+8b = n", and P(n): "n >= 14 -> -] a,b (- N, 3a+8b = n". - Code (C): Say precisely what your conjecture is. Do not use sentence fragments (e.g., do not say something like "14 cents or greater is the answer"; rather, say "it is possible to make every amount of postage of 14c or more using only 3c and 8c stamps.") Keep in mind that a conjecture is something whose truth or falsity we want to establish, so it must be a complete statement.