=========================================================================== CSC 236 Homework Assignment 1 -- Marking Scheme Fall 2009 =========================================================================== 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, be on the lookout for reasonable misinterpretations of the question and mark leniently when the solution is correct based on some reasonable implicit assumptions -- of course, this is open to your judgement about what is "reasonable", but that is one area where you should be more lenient. Also, 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). For solutions that are significantly different from the expected, just use the following basic general breakdown of marks: _F_ormat [roughly 33%]: proper format/structure for the answer, independently of the solution's correctness _I_dea [roughly 33%]: correct high-level idea/intuition for the answer, independently of the format or details provided _D_etails [roughly 33%]: each part of the solution is provided and correct, independently of the format 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. [20 marks] (a) [2 marks] _F_ormat [1 mark]: clear attempt to do as asked _D_etails [1 mark]: correct values (b) [4 marks] _F_ormat [1 mark]: clear attempt to prove result _I_dea [1 mark]: reasonable proof structure _D_etails [2 marks]: correct argument (c) [14 marks] _F_ormat [5 marks]: clear attempt to give an explicit value for d and to prove equation (1) by induction on n, including having the correct elements in the proof: attempt to define P(n), base case, inductive hypothesis, and inductive step _I_dea [5 marks]: correct value for d and definition of P(n), reasonable overall reasoning for the proof of the base case and inductive step _D_etails [4 marks]: correct proof of the base case and inductive step -- this was difficult: be lenient Marker's Comments / Error Codes / Common Errors: A1: 1 mark Writing (c + xy) / (d + xy) > c / d without saying anything about c, d. A2: 4 marks This is the most common error in proofs of question 1. p >= q does *not* imply p a >= q a, unless a is >= 0... 2. [15 marks] (Note: Codes between square brackets refer back to the "basic general breakdown of marks" above, e.g., "[1 F]" means "1 mark for Format".) _P_redicate [3 marks]: clear attempt to define P(n) explicitly [1 F] and correct definition [1 I; 1 D] -- give marks for the definition as long as the proof clearly makes use of a consistent statement, even if it is not defined explicitly (but no mark for format in this case) _H_ypothesis [2 marks]: I.H. clearly stated [1 F] and correct [1 D] _B_ase case [3 marks]: base case clearly present [1 F] and correct [1 I; 1 D] _S_tep [7 marks]: clear attempt to prove the appropriate inductive step [1 F] and clear use of the inductive hypothesis [1 F]; correct high-level proof [3 I]; correct proof details [2 D] Marker's Comments / Error Codes / Common Errors: B1: 1 mark Forgot to mention that a_1,...,a_k should be different in the predicate. B2: 1 mark If you give the form 1/k = 1/(k+1) + 1/(k)(k+1) and do not give a good reason why this procedure is finite. B3: 4 marks Forget to prove that a_1,...,a_k should be different in the proof. B4: 2-5 marks I.H. based on infinitely many things (i.e., 'suppose that for all q < r, q, r are rational numbers, P(q) is true.') 3. [15 marks] (Same as for Question 2.) Marker's Comments / Error Codes / Common Errors: C1: 1 mark Not consistent: use P(e) when e = RAE somewhere and use P(n), when n is the number of sub-expressions in RAE somewhere else. This is for the sake of format. [Instructor's note: But it is very important! You know from CSC165 the importance of expressing yourself clearly and precisely...] C2: 3 marks Assume that a RAE with (n+1) sub-expressions can be obtained by a RAE with n sub-expressions and another atomic. RAE (2+3)*(4+5) is a counter-example. [Instructor's note: If you made this mistake, please, please take the time to read *carefully* the "additional notes on induction" that I posted on the Lectures page following the lecture summary for Week 5.] 4. [15 marks] _F_ormat [5 marks]: correct structure for well ordering: proof by contradiction, use of well ordering to argue there is a smallest counter-example, argument that this leads to a contradiction _I_dea [5 marks]: reasonable high-level argument for base case(s) and inductive step _D_etails [5 marks]: proof is completely correct For students who answer using induction, use the marking scheme from Question 2 and divide the result by 3 (round up). Marker's Comments / Error Codes / Common Errors: D1: 4~5 marks Many students proved this: for all n, 2^{2n} - 1 = 0 (mod 3). Indeed, this is not the original problem. Students who proved this problem without showing that it is equivalent to the original problem, lost 4-5 points (depends on how clear the proof is). [Instructor's note: This is actually very generous -- I would have penalized this more, because it is a serious mistake. If you don't understand why, please come talk to me during office hours, or ask by email or on the bulletin board.] 5. [15 marks] (Same as for Question 2.) Marker's Comments / Error Codes / Common Errors: General comment: Many students have the right idea but fail to write down proofs clearly and consistently. It's really hard to read and judge unclear/ambiguous proofs. Students who think that their proof/format is correct but still lose marks should refer to the sample solution, to see what a well-stated proof is. [Instructor's note: Again, you should know from CSC165 the importance of expressing yourself clearly and precisely -- just like when you write code and a single incorrect character can make the difference between a correct program and an incorrect one, proofs must be written with care. But because there is no "proof compiler" that will do the checking for you, it means you have to be that much more careful yourself...] E1: 5 mark Consider the following Game: for each odd n, n people stand in cycle. When the game start, each person throws his/her water balloon to the one on his/her left hand side. Following your proof, this game still has a survivor, but in fact there's no survivor in this game. Now can you see why your proof is not correct? E2: 1-3 marks Simply ignore 2 players in the game with (n+2) players and suppose that the rest of the game is equivalent to the Game with n players. General Marker's Comments / Error Codes / Common Errors: Other kinds of error codes such as V1,V2,..., F1,F2,... correspond to Vague Claim, Format.