=========================================================================== CSC 165 Homework Assignment 3 -- Marking Scheme Winter 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. Remember that marking is not only about evaluating a student's performance, but also mostly 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). Your marking comments will be included in this marking scheme and posted on the course website so that students may look up the meaning of marking codes and understand how their work was marked. GENERAL ERRORS (marked negatively, in addition to any other errors): _N_ notation [up to 20%]: incorrect/undefined/ambiguous notation _V_ vagueness [up to 20%]: incorrect/unjustified/vague claim General Marker's Comments / Error Codes: 1. [12 marks] (a) [2 marks] _A_ answer [2 marks]: correct answer (b) [4 marks] _A_ answer [2 marks]: correct answer _J_ justification [2 marks]: reasonable justification that the answer *is* the worst-case (0 marks if there is no explanation about the input used) (c) [6 marks] _A_ answer [3 marks]: correct answer _A_MAIN_ [1 out of 3 marks]: correct answer for main loop _A_INT_ [2 out of 3 marks]: correct answer for internal loop _A_NOT_WORSE_ [-1 mark]: line 7 is counted too many times in (c) _J_ justification [3 marks]: reasonable justification that the answer *is* the worst-case _J_MAIN_ [1 out of 3 marks]: justification for the main loop _J_INT_ [2 out of 3 marks]: justification for internal loop Marker's Comments / Error Codes: _A_NOT_WORSE_ [-1 mark]: it is not the worse case _J_VAGUE_ [-1 mark]: the justification could be better by listing line #'s for example, or explaining why this is the **worst** case 2. [20 marks] _S_ structure [8 marks]: clear attempt to prove T(n) in O(n^2) and T(n) in \Omega(n^2), separately; clear attempt to give a general argument that t(E,n) in O(n^2) for any input E of size n (including the proper format for O); clear attempt to describe a specific input of size n that requires time \Omega(n^2) (including the proper format for \Omega) _S_WORST_ [2 marks]: trying to find the worst running time for inputs of size n _S_LEAST_ [2 marks]: trying to find an example input giving a running time of at least n^2 _S_O_ [2 marks]: structure for O(n^2) _S_OMEGA_ [2 marks]: structure for \Omega(n^2) _U_ upper bound [6 marks]: correct proof that T(n) is O(n^2) -- i.e., correct values for c, B and correct argument _U_T_ [3 marks]: correctly proving that t doesn't go above n _U_O_ [3 marks]: correct proof of T(n) in O(n^2) _L_ lower bound [6 marks]: correct proof that T(n) is \Omega(n^2) -- i.e., correct values for c, B and correct argument _L_T_ [3 marks]: proving that t becomes O(n) with the given input _L_O_ [3 marks]: correct proof of T(n) in \Omega(n^2) Marker's Comments / Error Codes: _UPPER_ [-2 marks]: significantly incorrect upper bound on T(n) _LOWER_ [-2 marks]: significantly incorrect lower bound on T(n) 3. [10 marks] _S_ structure [6 marks]: clear attempt to prove the statement; correct structure for using the assumption g in O(f); correct structure for proving g^2 in O(f^2) STR_1 [2 marks]: correct structure of g in O(f) STR_2 [2 marks]: correct structure of g^2 in O(f^2) _C_ content [4 marks]: correct values for c, B and correct argument _C_B_ [1 mark]: correct B _C_C_ [3 marks]: correct c Marker's Comments / Error Codes: _PROVE_ [maximum 5 marks for structure]: attempt to disprove _COMPL_ [-1 mark]: overly complicated structure _STR_ [-1 mark]: structure is correct but not standard _ALL_ [maximum 5 marks for structure]: proof is for specific f and g 4. [12 marks] The statement is false for functions g such that floor(g(n)) = 0 for some values of n; true for functions g such that floor(g(n)) > 0 for all n. Give full marks to both possibilities, because the question did not fully specify this... _S_ structure [6 marks]: clear attempt to prove or disprove the statement; correct structure for the proof or disproof, including the structure for proving/disproving floor(g) in \Omega(f) _S_A_ [2 marks]: attempt to prove or disprove For disproof: _S_1_ [2 marks]: proving g in \Omega(f) for some f,g _S_2_ [2 marks]: proving floor(g) not in \Omega(f) for the same f,g For proof : _S_1_ [2 marks]: assume that g in \Omega(f) for arbitrary f,g _S_2_ [2 marks]: prove that floor(g) in \Omega(f) for the same f,g _C_ content [6 marks]: correct proof or disproof (same as above but with C prefix) Marker's Comments / Error Codes: - Most people who tried to prove it got C_2 (-2) for not being able to prove it correctly, since the statement is generally false. - I deducted 2 marks for choosing functions that won't work for proof/disproof. 5. [8 marks] _A_ answer [3 marks]: correct answer _C_ calculation [5 marks]: correct calculation/explanation Marker's Comments / Error Codes: _SIGN_ [-1 mark]: didn't consider negative numbers 6. [6 marks] _A_ answer [2 marks]: correct answer _E_ example [4 marks]: correct counter-example and explanation Marker's Comments / Error Codes: _EX_ [-1 mark]: no example with numbers is given _ERR_ [-1 mark]: small errors in computations or incorrect statements 7. [12 marks] _A_ answer [4 marks]: correct answer _J_ justification [8 marks]: correct computation and explanation [2 marks]: bound on absolute error [2 marks]: bound on denominator [-2 marks]: not understanding that we round to **zero** Marker's Comments / Error Codes: _ERR_ [1 mark]: small errors in computations or incorrect statements