Grading Scheme for Homework 2 A student gets 20% for writing "I do not know how to solve this problem". If a student gives more than 1 answer to a problem, only one answer is chosen arbitrarily for grading. --------------------------------------------------------------- Question 2: 10 points 3 points for algorithm 3: A correct algorithm 2: Some minor errors or a bit too complicated or inefficient For example, the code finds the number of songs but does not output which songs are to be loaded 1: The algorithm does not work, but is understandable 0: Really sloppy, impossible to understand, should have been obvious that the code does not work 5 points for proof 5: A completely correct and concise proof 4: Some minor details missing or the proof is a bit convoluted and hard to read 3: Major errors with the proof, but the idea is correct 2: The proof idea is wrong, but the student shows some understanding 1: Not a proof (for example, it just describes what the algorithm does) or "I don't know" 0: Garbage. You have no idea what they are writing 2 points for running time 1 point for accurately stating the running time of their algorithm - they lose the point if they overstate the running time 1 point for justifying their running time --------------------------------------------------------------- Question 5: 10 points 3 points for algorithm 3: A correct algorithm 2: Some minor errors or a bit too complicated or inefficient A common error in this problem will probably be in the use of data structures Another error is that the code does not output the order to merge, just the overall risk 1: The algorithm does not work, but is understandable 0: Really sloppy, impossible to understand, should have been obvious that the code does not work 5 points for proof 5: A completely correct and concise proof 4: Some minor details missing or the proof is a bit convoluted and hard to read 3: Major errors with the proof, but the idea is correct 2: The proof idea is wrong, but the student shows some understanding 1: Not a proof (for example, it just describes what the algorithm does) or "I don't know" 0: Garbage. You have no idea what they are writing 2 points for running time 1 point for accurately stating the running time of their algorithm - they lose the point if they overstate the running time 1 point for justifying their running time --------------------------------------------------------------- Question 7: 10 points 5 points for algorithm 5: A correct algorithm 4: Minor errors or inefficient For example: the student does not extract the solution from the table. Or, the student fails to include a "base" case in the table so the algorithm will not work 3: At least it is D.P. and a reasonable attempt, or it is an exponential (& correct) divide and conquer Example: The student only lists the recurrence and not how to build the table 2: A "correct" greedy algorithm or an unreasonable D.P. attempt or a good attempt but wrong divide and conquer Example: at least they are trying to use a table of the proper size to store subproblem solutions 1: An algorithm that clearly does not work 0: You cannot understand it, garbage, or an incorrect algorithm which in no way follows one of our 4 techniques 3 points for proof 3: A good proof. The student should prove the recurrence gives the optimal answer, and they should either write a short justification that their algorithm properly implements the recurrence and the procedure to extract the solution is correct, or these facts should be obvious from how they wrote their algorithm. 2: Anything remotely reasonable Examples: It is not obvious that their code implements the recurrence or extracts the solution. They don't really prove the recurrence is correct. 1: Clearly wrong Examples: They try valiantly to prove their greedy solution correct. They do not come close to proving the recurrence. 0: Garbage 2 points for running time 1 point for accurately stating the running time of their algorithm - they lose the point if they overstate the running time 1 point for justifying their running time --------------------------------------------------------------- Question 11: 10 points 8 points for showing how program works The student should give a series of diagrams or descriptions. You should be able to read through their answer quickly because at each step, it should be clear what the augmenting path is. Thus, the students will need some way of indicating the flow, capacity, and/or residual at each step so that you can easily see that each augmenting path is correct. If you cannot easily trace the running of the algorithm, deduct marks for the extra effort needed on your part. Deduct 1 point for one minor error, 2 points for multiple minor errors. A minor error is something which does not affect how the algorithm works. For example: incorrectly labeled flow/residual Deduct 2 points for one major error, 4 points for multiple major errors. A major error is something which does affect how the algorithm works. For example: choosing an incorrect augmenting path, or omitting an entire step in the algorithm. Deduct 2 points if you find their method of tracing the algorithm a little confusing, Deduct 4 points if you find their method of tracing the algorithm very difficult to follow or understand. Please also use the following minimum scores: If an answer is mostly correct, do not give a score less than 4. In an answer shows some knowledge of the algorithm, do not give a score less than 2. If you have no idea what the student is doing, give a 0. 2 points for cut 2: a correct minimal cut 1: not a minimal cut, but close (ex: maybe they didn't notice one extra edge) 0: clearly not a minimal cut --------------------------------------------------------------- Grader comments: Common mistakes: Question 2) Many students had the following invalid argument: "... In this case T_i = T_{i-1}. From I.H., T_{i-1} is promising. So, T_i is promising." Why should the optimal extension of T_{i-1} not include song S_i? Question 11) Some students assumed the capacity of a cut to be the summation over the flows from one part to the other. In this case, the capacity of every cut would be equal to the value of the considered flow.