Posted by: jeff | October 13, 2009

The usual rules apply here; if you have any questions about the point breakdown, you can contact me via email or with a comment on this post.

Q1 (Ch.3 Ex.3 – 80 pts.): 20 pts. for Algorithm ideas, 30 pts. for the Algorithm, 5 pts. for a proof idea*, 15 pts. for a proof of correctness, and 10 pts. for an analysis of run time*
Q2 (Ch.3 Ex.9 – 20 pts.): 5 pts. for the proof idea, 10 pts. for the proof, and 5 pts. for explaining and analyzing the algorithm

* Please note: there has been a minor change in the rubric – inclusion of a proof idea component, and a corresponding reduction in points for the analysis of run time on question 1

## Responses

1. for Q1 it says 15 points for proof correctness but nothing is stated about proof idea. Do we need to include a proof idea?

• Dale,

Yes, by default you need to write a proof idea. See item 4 in the homework policy document.

2. Exercise 9 in Chapter 3 is asking for an algorithm. I am guessing Jeff’s rubric for number 2 is suppose to read algorithm idea, and then algorithm, not proof idea, and then proof.

• Eric,

I am still in Germany and do not have access to the book. However, from what I remember the problem asks for *both* a proof that a node with the required property exists and an algorithm to find such a vertex. So Jeff’s rubric makes sense.

However, I’ll let Jeff confirm this.

3. Yes, Dr. Rudra is correct. If you read the question, the second to last sentence (the one before the parentheses) says: “Show that there must exist some node v, not equal to either s or t, such that deleting v from G destroys all s-t paths.” The last sentence asks for an algorithm. So you have to first prove that such a v exists, then give an algorithm to find it. If you can prove it must exist, the algorithm flows pretty naturally from the proof.