=========================================================================== CSC 373 Homework Assignment 1 -- 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 1. [22 marks] (a) [5 marks] _O_rdering [2 marks]: reasonable (and specific) greedy ordering _C_ounter-example [3 marks]: correct counter-example (including justification) (b) [17 marks] _S_tructure [3 marks]: clear attempt to give an explicit greedy algorithm to solve the problem, to analyze its running time, and to *prove* its correctness by defining a notion of "promising" and showing that each greedy partial solution is promising, by induction _A_lgorithm [4 marks]: clear and correct greedy algorithm; correctly handles inputs for which there is no solution _R_untime [2 marks]: correct analysis of algorithm's runtime _P_roof [8 marks]: good definition of "promising"; correct proof by induction that each partial solution produced by greedy is promising, including final justification that overall solution is optimal; good justification that algorithm produces reasonable output when there is no solution 2. [12 marks] (a) [8 marks] _S_tructure [2 marks]: clear attempt to define "promising", to prove that each partial solution produced by greedy is promising, and to justify that final solution is optimal _P_roof [6 marks]: good definition of "promising" and correct proof by induction that each partial solution produced by greedy is promising, including final justification that overall solution is optimal (b) [4 marks] _A_nswer [1 mark]: clear attempt to give an explicit counter-example _C_ounter-example [3 marks]: correct counter-example (including justification) (c) [8 BONUS marks] NOTE: Give full marks only for conditions that are exceptionally elegant/general and that are well-justified. _C_ondition [3 marks]: good condition: generalizes the one from part (a) and is easy to verify for any set of denominations, independently of the greedy algorithm _J_ustification [5 marks]: good argument that the condition is correct 3. [20 marks] (a) [3 marks] _C_ounter-example [3 marks]: correct counter-example (including justification) (b) [4 marks] _A_nswer [1 mark]: clear attempt to give an explicit counter-example _C_ounter-example [3 marks]: correct counter-example (including justification) (c) [13 marks] _S_tructure [3 marks]: clear attempt to give an explicit greedy algorithm to solve the problem, to analyze its running time, and to prove its correctness _A_lgorithm [2 marks]: clear and correct linear-time algorithm _R_untime [1 mark]: correct analysis of algorithm's runtime _C_orrectness [7 marks]: good proof of correctness for the algorithm 4. [26 marks] (a) [8 marks] _S_tructure [2 marks]: clear attempt to give an explicit algorithm and either to prove its correctness (following the appropriate format) or to give an explicit counter-example to show it does not always yield optimal solutions _A_lgorithm [3 marks]: correct greedy algorithm _C_ounter-example [3 marks]: correct counter-example (including justification) (b) [18 marks] _S_tructure [4 marks]: clear attempt to define arrays of values related to the problem, to give recurrence relations for the array values, to justify the recurrences based on the recursive structure of optimal solutions, to give an algorithm to compute the array values bottom-up and to generate an actual solution from those values, to analyze the runtime of the algorithm _A_rrays [3 marks]: reasonable definition of the arrays _R_ecurrences [4 marks]: correct recurrences for the arrays, including appropriate base cases _J_ustification [2 marks]: good justification of correctness for the recurrences _B_ottom-up algorithm [5 marks]: correct bottom-up algorithm to compute array values and, especially, to generate a solution from those values