=========================================================================== CSC 236 Homework Assignment 2 -- 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. [18 marks] (a) [6 marks] _F_ormat [2 marks]: clear attempt to write down exact recurrence relations for T(n) and B(n), and to justify their correctness -- independently of whether or not they are actually correct _I_dea [2 marks]: correct recurrences for T(n) and B(n), including base case(s) -- independently of how well they are justified _D_etails [2 marks]: good justification for each recurrence's correctness -- including the computation of the input size for the recursive calls (b) [12 marks] IMPORTANT NOTE: Mark this with respect to the recurrence given in part (a), i.e., if the recurrence is slightly incorrect, but it is solved correctly, give full marks on this part. _F_ormat [2 marks]: clear attempt to prove an inequality of the form T(n) >= B(n) (or T(n) <= B(n)) for all n "large enough", by induction on n -- whether or not the inequality and proof are correct _I_dea [5 marks]: correct approximate values for T(n) and B(n) obtained, and correct inequality derived. _D_etails [5 marks]: correct proof of the inequality for the exact values of T(n) and B(n) Marker's Comments / Error Codes / Common Errors: D1 [-1 mark]: In part(a), it is just assumed that the input size for the recursive call is ceil(n/3) for T(n), and ceil(n/2) for B(n), without showing how these values are computed. D2 [-0.5 mark]: In part(a), it is ignored that the formulas for computing c and d and m are 'integer' division. D3 [-2 marks]: In some papers it is argued that B(n) = \Theta(log_2 n) and T(n) = \Theta(log_3 n), and it is used to conclude that B(n) performs more operation than T(n). D4 [-1.5 marks]: The inequality is proved for approximate values of T(n) and B(n), and it is implicitly assumed that the approximate values are equal to the exact values. I1 [-1 mark]: Base cases for T(n) and B(n) are not computed. 2. [16 marks] (a) [3 marks] _E_rror [marked negatively]: -1 for each error/missing element in the recurrence (b) [5 marks] IMPORTANT NOTE: Mark this with respect to the recurrence given in part (a), i.e., if the recurrence is slightly incorrect, but it is solved correctly, give full marks on this part and the next one. _F_ormat [1 mark]: clear attempt to perform repeated substitution following the style used in class: substitute repeatedly into the recurrence, state the general form, solve for the number of substitutions required to reach the recurrence's base case -- regardless of whether or not substitution is done correctly _I_dea [2 marks]: correct general term and correct base case reached -- even if there are minor errors in the substitution or the expressions are not simplified as much as possible _D_etails [2 marks]: substitution done correctly throughout, and final expression suitably simplified (c) [8 marks] _F_ormat [3 marks]: clear attempt to prove a closed-form expression from the recurrence, by induction, including clear and correct format for the induction _I_dea [2 marks]: correct high-level proof for base case and inductive step -- even if proof is poorly written _D_etails [3 marks]: proof well-written; all steps present and correct Marker's Comments / Error Codes / Common Errors: Common Error: In many papers this recurrence was used: A_n = A_{n-1} * I - P. In this case, 1 mark is reduced (error code E), and the error was neglected in other parts of the question. 3. [46 marks] (a) [23 marks] _F_ormat [5 marks]: clear attempt to prove the correctness of the recursive algorithm (i.e., that the algorithm terminates and the postcondition holds for every input that satisfies the precondition) by induction on the size of the input, to prove the correctness of the loop as part of this (i.e., to prove that the loop terminates and to prove a loop invariant by iduction on the number of iterations completed), and clear inductive structure for these proofs -- these marks are for the structure only, irrespective of whether the proofs are correct Recursive Correctness [8 marks]: _I_dea [5 marks]: correct high-level argument for the recursive correctness proof, including making appropriate use of the loop invariant or loop postcondition _D_etails [3 marks]: every step of the argument is correct Iterative Correctness [10 marks]: _LI_ [3 marks]: correct loop invariant -- whether or not it is proved correctly _T_ermination [2 marks]: correct argument for loop termination _P_roof [5 marks]: correct proof of the loop invariant (b) [23 marks] _F_ormat [5 marks]: clear attempt to prove the correctness of the the loops by showing that they terminate and proving loop invariants by iduction on the number of iterations completed, and clear inductive structure for these proofs -- these marks are for the structure only, irrespective of whether the proofs are correct Outer Loop [9 marks]: _LI_ [3 marks]: correct loop invariant -- whether or not it is proved correctly _T_ermination [1 mark]: correct argument for loop termination _P_roof [5 marks]: correct proof of the loop invariant Inner Loop [9 marks]: _LI_ [3 marks]: correct loop invariant -- whether or not it is proved correctly _T_ermination [1 mark]: correct argument for loop termination _P_roof [5 marks]: correct proof of the loop invariant Marker's Comments / Error Codes / Common Errors: Common Error: Some students only considered and proved min_k <= min_{k-1} as the loop invariant (they just argued that both inner and outer loop do not assign any min value that is bigger than the previous min). And they completely ignored to show how that implies the loop postcondition and how that is used to prove the correctness of the algorithm. For each instance of the error (inner or outer loop) they lost 3 marks. Another Common Error (error code T): In many papars, termination was not proved explicitly. (Perhaps it was assumed to be obvious in for-loops). But to follow the grading guide, those who ignored proving termination unfortunately lost the mark of that part.