=========================================================================== CSC 236 Homework Exercise 4 -- Marking Scheme Fall 2009 =========================================================================== IMPORTANT NOTE: Exercise 4 was marked late because the original marker was unable to do the work, for various personal reasons. Unfortunately, the "replacement marker" did not have time to set up his CDF account to do the marking electronically, and decided to carry out the marking on paper. This means that your marked with is *not* attached to this email -- rather, it will be handed back during the next lecture. Alternatively, you can drop by my office during any of my regular office hours to pick it up. Now back to the regular marking scheme stuff -- with detailed marker's comments near the bottom... 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 2% of the final grade and your marking time is very limited, so your marking must be coarse -- unfortunately, you do not have time to make fine distinctions, so do not give or take away anything smaller than 0.5 marks. Be on the lookout for misinterpretations of the question and don't take off too many marks for making incorrect but 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 -- within the limitations imposed by your marking time, of course. 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). Please record any such marking codes or common errors below. 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): _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 1. [2 marks] _R_esult [1 mark]: correct result obtained from the Master Theorem, including picking the correct case that applies _J_ustification [1 mark]: correct justification that the Master Theorem applies and correct values for the parameters 2. [4 marks] _F_ormat [1 mark]: clear attempt to substitute repeatedly into the expression for f(n), to give the general expression obtained after i substitutions, to solve for i in order to reach a base case for f(), and to simplify the resulting expression -- give marks for this even if the substitution was done incorrectly _I_dea [1 mark]: substitution performed correctly at each step -- even if some of the algebra was done incorrectly _D_etails [2 marks]: correct expressions obtained at each step, including the final simplifications -- it's OK if the final expression is not simplified exactly as in the sample solutions, but there should be no summation symbol remaining Marker's Comments / Error Codes: In addition to the written comments I've left you, there were two kinds of mistakes, both for part 2, which were so common that I decided to just write a code (written in pencil) and refer you to this document. If some penciled code appears on your printed assignment which is not included below (e.g., T, A, L, etc.), ignore it -- that was just a preliminary note I made to myself on a first pass through the stack of assignments. S: We decided to take off some marks if your final expression contained a sumation symbol. But I only took off .35 points. Since you proved in part 1 that f(n) is in Theta(n^{log_b a}), there is really only one way to improve on that -- namely by giving explicit constants c1, c2, n0 such that for all n > n0: c1 n^{log_b a} < f(n) < c2 n^{log_b a}. You weren't asked to do that -- instead you were given the simpler, though more open-ended task of giving a single expression which appears to approximate f(n) well. An ideal expression makes it clear what the constant on n^{log_b a} is, and an expression which contains a summation over a number (which depends on n) of non-constant terms, is not such an ideal expression. [Instructor's comment: Here is another way to think about this, to see why it's important. The recurrence that you start with is a perfectly fine way to compute the values of f(n): just write a short recursive function and you're done. The problem with this is that it doesn't give us a single expression that we can work with, and that's why we want to get rid of the recursion. When you perform repeated substitution, you are "unrolling" the recursion. If you do this, but you leave the result still "rolled up" inside a summation instead, then all you've done is taken a recursive loop, and translated it into an equivalent iterative loop. But you're no closer to having a single expression that we can plug n into directly: you still need to carry out some kind of loop in order to evaluate f(n). So in general, we always try to eliminate summations from our final expressions.] V: You made a "variable-binding" related error (I'll explain what I mean shortly), which greatly simplified your task. I marked off heavily. This is a kind of error that you should never make. Here is how it happens: In this problem, you might have defined f'(n) := 2 f(n/3) + sqrt(n) to be an approximation of f, and then you give a few equivalent definitions of f' f'_2(n) := f'_3(n) := f'_4(n) := You recognize a pattern, and then assert (you weren't asked to give a proof) that for all i f'_i(n) := is also a definition equivalent to f'. Note that variable 'i' is "bound". It starts to be bound right at "for all i", and you might as well assume it stays bound. Its meaning is fixed. What some of you did was, in your definition of f'_i, you had a summation symbol, and you **reused** the variable i, like this: f'_i(n) := ... + \sum_{i=1}^{i-1} That is asking for trouble. Just don't ever do that. Technically, it doesn't necessarily mean you'll make an error, but in fact everyone who did it did end up making an error because of it. At best, it is terrible style. Instead, use a different variable, like this: f'_i(n) := ... + sum_{j=1}^{i-1}