=========================================================================== CSC 373 Homework Assignment 2 -- Marking Scheme Fall 2008 =========================================================================== 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. And 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). 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 Outline for dynamic programming algorithms: Step 1. Define a table of values (clearly state the meaning of each table entry, in particular, which specific subproblem it corresponds to and what specific value it stores). Step 2. Give a recurrence for the values in the table, and justify that your recurrence is correct (by reasoning about the recursive structure of optimal solutions). Step 3. Give a bottom-up algorithm that computes the values in the table following the recurrence, and analyze the runtime of your algorithm. Step 4. Give an algorithm that reconstructs an optimal solution from the table values (include an explanation of any additional information required and a brief justification that your solution is constructed correctly, as well as a brief analysis of your algorithm's runtime). 1. [20 marks] _S_tructure [4 marks]: clear attempt to follow the outline above, except for Step 4 (not required for this question) _T_able [3 marks]: correct and well-defined table _R_ecurrence [7 marks]: correct recurrence for table values, including reasonable justification/explanation of correctness _B_ottom-up algorithm [5 marks]: good algorithm to compute table values, including brief justification of correctness and runtime analysis -- give full marks for correctly following recurrence, even if recurrence is incorrect _A_nswer [1 mark]: correct overall answer returned, based on table definition (even if recurrence/algorithm has errors) Marker's Comments: [IJ] -- Insufficient Justification; penalty depends on how much justification is lacking. This was marked more harshly in cases where the answer is wrong and/or hard to understand. [BR] -- Runtime for the bottom up algorithm; 0.5 marks for stating the correct runtime, 0.5 for justification. [-0.5 AB] -- Array Bounds: when defining the array, the size of the array (and the bounds for parameters) were not specified. - When analysing runtime, a lot of people had loops that iterated m times, and then stated that the runtime of those is O(n). This was not penalized for this question, because in this case m < n, and any algorithm that runs in O(m) time surely runs in O(n). However, in some other questions this kind of thing does actually play a role. Moral: When analysing runtime, BE VERY CAREFUL ABOUT THE QUANTITIES INVOLVED, and make sure you are clear on what your variables mean! - A lot of people's algorithms returned the order of the cuts, and not the actual cost. This was not penalized per se, but people did lose marks [-1A] if they did not state how to get the minimum cost from the array. Be sure to read the question and understand what it asks of you! - In many answers people did not explicitely state whether the bounds are inclusive or exclusive. For example, saying "cut the string from i to j", without specifying what it means: do you actually include s_i and s_j? This was not normally penalized, unless it was unclear or was used inconsistently. 2. [20 marks] _S_tructure [4 marks]: clear attempt to follow the outline above _T_able [3 marks]: correct and well-defined table _R_ecurrence [6 marks]: correct recurrence for table values, including reasonable justification/explanation of correctness _B_ottom-up algorithm [3 marks]: good algorithm to compute table values, including brief justification of correctness and runtime analysis -- give full marks for correctly following recurrence, even if recurrence is incorrect _C_onstruction of solution [4 marks]: correct algorithm to construct final solution, brief explanation of additional information stored, justification of correctness, and runtime analysis Marker's Comments: This question was done worse than the other ones on this assignment; it was also the one with the most varied answers. - For this question, there were a lot of answers that were needlessly complicated. This by itself was not penalized, unless it showed lack of understanding or led to other errors (which it very often did). After you've written the algorithm/recurrence (or even while writing it), ask yourself: "Do I really need this as a special case? Would it already be handled automatically by another case? Why do I need to do this? What does this help me achieve?" Then you can avoid doing things like pointless sorting before the rest of the algorithm, calculating values that are never used or creating redundant special cases. Many people explicitely incorporated the knowledge that there must be at least one machine of each type -- which led to many special cases, not all of which were covered by the algorithm; for example, what if the budget is not enough to buy one machine of each type? Note that those special cases are automatically handled by optimization, because any nonzero probability would be preferred to the probability of 0; see sample solutions for a simple algorithm. 3. [20 marks] (a) _T_ables [3 marks]: correct and well-defined tables (should include at least cases "in" and "out", or equivalent) (b) _R_ecurrence [8 marks]: correct recurrence for table values, including reasonable justification/explanation of correctness (c) _A_nswer [1 mark]: correct overall answer returned, based on table definition (even if recurrence has errors) (d) _C_onstruction of solution [5 marks]: correct algorithm to construct final solution, explanation of additional information stored, and justification of correctness (e) _T_race [3 marks]: clear and correct tables of values for the tree, and trace of algorithm's behaviour on the tree Marker's Comments: [-0.5 PA] -- Parent is mentioned in the subproblem statement. For example, "This is the minimum weight of a dominating set rooted at v where v's parent is in the set." This is wrong, because 1) the subproblem should not concern itself with anything outside the subproblem, and 2) the recurrence is calculated bottom-up, so you don't have information about the parent while calculating the values for the child. [-1 II] -- Insufficient Information - the table in part 1 does not contain enough information to effectively propagate it. Most often, something analogous to the table Pseudo from the sample solutions was missing. [-1 FC] -- Forcing the Children of an included node to be outside of the dominating set. Consider a tree where each node has a single child, with weights: (5)-(1)-(1)-(5). The minimum weight is 2, but if you force the alteration, you cannot do better than 6. [-3 PC] -- Misses the case where neither parent not any of its children are included. Example, (1)-(5)-(5)-(1). The minimum weight is 2, but many algorithms would find a set with weight 6. [-2 ES] -- The algorithm does not ensure the proper structure: while recovering the set, some nodes might be missing. 4. [20 marks] _S_tructure [4 marks]: clear attempt to give a divide-and-conquer algorithm, to justify its correctness, and to analyze its runtime using the Master Theorem _H_igh-level algorithm [6 marks]: correct algorithm, at a high level _I_mplementation [4 marks]: correct implementation of high-level idea that runs within the required time bound _J_ustification [4 marks]: good justification of algorithm's correctness _R_untime [2 marks]: correct analysis of algorithm's runtime Marker's Comments: This question was surprisingly well done!