Posted by: **jeff** | October 13, 2009

## HW 5 Grading Rubric

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

### Like this:

Like Loading...

*Related*

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

By:

Dale Brosiuson October 14, 2009at 12:10 am

Dale,

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

By:

atrion October 14, 2009at 6:09 am

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.

By:

Ericon October 15, 2009at 7:56 pm

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.

By:

atrion October 15, 2009at 11:02 pm

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.

By:

jeffdelmericoon October 16, 2009at 12:33 am