Notes from the grader: When proving NP-completeness, some of the proofs of "iff" were a bit sketchy. Be sure to state (for yourself) _exactly_ what it is that you are trying to prove, and prove it. Most people had minor deductions for this. In particular, the solutions I provided are only sketches to present the general idea. Grading Scheme for Homework 3 Question 1: 10 points For a completely correct answer, they need to understand how the APSP algorithm works. Namely, that it is a dynamic programming algorithm and it says that for any shortest path from u->v, if the path is not a single edge, then there exists a vertex w on the u->v path such that u->w and w->v are shortest paths. Now, show why this does not hold for longest paths. 10: Any answer which demonstrates the above enough to convince you they understand the problem. 8: On the right track but too vague or some errors so you are not convinced they understand it. For example, they use some good counter examples, but do not prove in general. 7: They use a single good counter example, but do not argue in general. 6: They give a reasonable example of a trivial change to the algorithm and show that this algorithm does not work, but they do not show in general that any algorithm based on APSP cannot work. (Ex. their argument uses a counter example for their case, but do not argue about any general APLP algorithm.) 5: They prove LONGEST PATH is NP-complete. This is only half an answer because it only shows the algorithm can't work so long as P <> NP. If P=NP, then maybe the algorithm works! 3: They try to probe LONGEST PATH is NP-complete but there are errors OR they try to use a counter example, but it is obviously wrong. 1: You do not understand their answer at all or they clearly have no understanding of the problem. --------------------------------------------------------------- Question 4: 10 points The points are divided as follows: 2 points for proving that the problem is in NP 2 points for doing a proper transformation 2 points for showing the transformation is polynomial 2 points for proving the if direction 2 points for proving the only-if direction 1. Does the answer show the problem is in NP? 0 if they forgot or it is clearly wrong 1 if it has some errors 2 if it is correct 2. Does the problem have a correct transformation FROM a NP-complete problem 0 the transformation is in the wrong direction, they do not use a NP-complete problem, anything else which is completely wrong 1 right idea but errors in what they did for example: the transformation only works with some but not all instances of the NP-complete problem 2 correct 3. Do they prove the transformation is polynomial 0 omitted 1 done but is incorrect 2 correct 4. Do they provide a proof in the if direction 0 omitted or the proof is clearly wrong for example, the transformation is clearly wrong and the resulting proof makes no sense 1 errors in the proof for example, the transformation is wrong, but the student makes a valiant effort to do the proof 2 correct 5. Do they provide a proof in the only-if direction Note: If they are careful, they could have proven "if and only if" in one step. 0 omitted or the proof is clearly wrong 1 errors in the proof 2 correct --------------------------------------------------------------- Question 6: 10 points The points are divided as follows: 2 points for proving that the problem is in NP 2 points for doing a proper transformation 2 points for showing the transformation is polynomial 2 points for proving the if direction 2 points for proving the only-if direction 1. Does the answer show the problem is in NP? 0 if they forgot or it is clearly wrong 1 if it has some errors 2 if it is correct 2. Does the problem have a correct transformation FROM a NP-complete problem 0 the transformation is in the wrong direction, they do not use a NP-complete problem, anything else which is completely wrong 1 right idea but errors in what they did for example: the transformation only works with some but not all instances of the NP-complete problem 2 correct 3. Do they prove the transformation is polynomial 0 omitted 1 done but is incorrect 2 correct 4. Do they provide a proof in the if direction 0 omitted or the proof is clearly wrong for example, the transformation is clearly wrong and the resulting proof makes no sense 1 errors in the proof for example, the transformation is wrong, but the student makes a valiant effort to do the proof 2 correct 5. Do they provide a proof in the only-if direction Note: If they are careful, they could have proven "if and only if" in one step. 0 omitted or the proof is clearly wrong 1 errors in the proof 2 correct --------------------------------------------------------------- Question 8: 10 points If the prove the problem is NP-complete: The points are divided as follows: 2 points for proving that the problem is in NP 2 points for doing a proper transformation 2 points for showing the transformation is polynomial 2 points for proving the if direction 2 points for proving the only-if direction 1. Does the answer show the problem is in NP? 0 if they forgot or it is clearly wrong 1 if it has some errors 2 if it is correct 2. Does the problem have a correct transformation FROM a NP-complete problem 0 the transformation is in the wrong direction, they do not use a NP-complete problem, anything else which is completely wrong 1 right idea but errors in what they did for example: the transformation only works with some but not all instances of the NP-complete problem 2 correct 3. Do they prove the transformation is polynomial 0 omitted 1 done but is incorrect 2 correct 4. Do they provide a proof in the if direction 0 omitted or the proof is clearly wrong for example, the transformation is clearly wrong and the resulting proof makes no sense 1 errors in the proof for example, the transformation is wrong, but the student makes a valiant effort to do the proof 2 correct 5. Do they provide a proof in the only-if direction Note: If they are careful, they could have proven "if and only if" in one step. 0 omitted or the proof is clearly wrong 1 errors in the proof 2 correct If they give an algorithm for the problem: Is the algorithm correct (2 points) (Note: The problem is NP-hard so a correct algorithm cannot be polynomial.) 0 the algorithm clearly cannot work 1 it does not seem that the algorithm will work or it is unclear because the student does not give enough description to convince you it will work - still it was a reasonable attempt 2 the algorithm works Do they correctly give the running time (2 points) 0 no running time listed, or the one given is clearly wrong 1 a correct unjustified running time or one that is justified but is not tight. 2 a correct and justified running time Do they state that whether or not the algorithm is feasible because it is faster or slower that O(n^2)? (2 points) 0 they did not do this 2 they did this