CSC236 -- Fall 2007 -- Grading Scheme for Assignment 1 ------------------------------------------------------ NOTE TO STUDENTS: You will find below the marking scheme used in Problem Set 1, 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: For each question, I list solution elements with associated codes (for writing on student papers) and 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. You will likely encounter other common errors, e.g., using P(n) to denote both a statement and a number at the same time (ambiguous notation, a problem serious enough to take marks off in every question where it occurs), writing the inductive hypothesis as "suppose for all n" (which I would classify as incorrect use of notation), or a proof where the inductive hypothesis does not connect with the base case(s) (which should lose the mark(s) for hypothesis, and more if it cannot be dismissed as a typographical error), etc. Simply keep track of the most common ones, 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) -- make sure you keep a list of any new codes you use, their meaning, and the associated number of marks, so that we can make this information available. Be picky! Students are responsible for showing that they understand and for writing up their answers clearly and precisely. Keep in mind that they've had the time to ask questions, to formulate their answers, and to write them up. Also keep in mind the Faculty's guidelines for the meaning of grades: Submission bonuses (+5%) or penalties (-10%) are to be computed as a percentage of the grade obtained on the assignment, NOT as a percentage of the total -- e.g., a grade of 34/40 with penalty of -10% gets a final mark of 30.6 = 34 - 3.4. General errors (marked negatively): N- Notation: incorrect/ambiguous notation. [up to 4] A- Assumption: invalid implicit assumption. [up to 4] V- Vague: incorrect/unjustified/vague claim. [up to 4] Generel marker's comments: - I put either a circle or a cross on the question number. An answer marked with a circle could be corrected or extended to a correct solution, and thus is marked by deduction according to the "solution elements" in the marking scheme. An answer with a cross is not regarded as an incomplete version of a valid proof (thus hard to identify which part is which element), and therefore marked additively from 0. 1. Solution elements: C- Conjecture: correct and clearly stated conjecture. [2] F- Format: correct proof format (definition of P(n), base case(s), inductive hypothesis, inductive step, conclusion). [2] B- Base case(s): correct proof of base case(s). [1] H- Hypothesis: correct inductive hypothesis. [1] S- Step: correct proof of inductive step. [4] Marker's comments: - Since most students at least tried to write in the format of induction, the most common mistake was incorrect use of words. For example, connectivity is a number associated to a hub, but they talked about connectivity of a link or of a network. Also, "twice the n network" (to really mean twice the number of links), "C(n) holds" (to mean that the number C(n) satisfies a certain property), etc. Many used quantifiers incorrectly, both in English and in symbols. Many even wrote statements with unbound variables. I'm not sure if this is supposed to be part of the course, but you should probably remind them of the meaning of quantifiers. - Another very common mistake was to begin the proof by "Let C(n) be the sum of connectivities of all hubs in a network with n links." This notation assumes that the sum of connectivities can be expressed as a function of the number of links alone, independently of the structure of the network. But this is part of what they should prove. 2. Solution elements: F- Format: correct proof format (definition of P(n), base case(s), inductive hypothesis, inductive step, conclusion). [2] B- Base case(s): correct proof of base case(s). [2] H- Hypothesis: correct inductive hypothesis. [1] S- Step: correct proof of inductive step. [5] Marker's comments: - Seven students answered (essentially) correctly with the intended solution. Most students tried to show "P(n) --> P(n + 11)" in the induction step, where P(n) is either the statement as is or the strengthened version. To do so, some of them used the (wrong) relation S_i(n + 11) = S_i(n) + 1 in the proof, which is only true when there is no carry in the addition n + 11. Others were careful enough to attempt, though unsuccessfully, a separate analysis in the cases with carry. Five students succeeded in completely analyzing how the carries propagate and affect S_i(n). They got the full mark (marked "Another Solution"), but since this is an unnatural way to use induction, I did not give credit for any partial progress toward this solution. - Some students did not seem to know the mod notation, and some mixed up the two usages of mod (as an equivalence relation and as a binary operator). - The hint suggested they prove a "strong (i.e. precise) statement." Many students seem to have taken the word "precise" the wrong way and attempted to state the same thing in a more formal way, e.g., just replacing "n is a multiple of 11" by "exists k in Z, n = 11k." 3. Solution elements: R- Recurrence: correct recurrence, including base case(s). [2] J- Justification: good justification of base case(s) and recursive case (in general terms). [3] Marker's comments: - Most students did well on this (except that many did not mention the base cases). 4. Solution elements: R- Recurrence: correct recurrence, including base case(s) -- should mention even values of n. [4] J- Justification: good justification of base case(s) and recursive case (in general terms). [4] F- Format: correct proof format (definition of P(n), base case(s), inductive hypothesis, inductive step, conclusion). [2] B- Base case(s): correct proof of base case(s). [1] H- Hypothesis: correct inductive hypothesis. [1] S- Step: correct proof of inductive step. [3] Marker's comments: - Most students who answered the question almost correctly made the same mistake, for which I penalized 1 point: In the induction step, they pick out the first and last terms to lower bound the summation. But this does not work for n = 3 because they are the same term. So the case n = 3 needs to be done in the base case.