Posted by: **jeff** | September 28, 2010

## HW3 Grading Rubric

1) 10 points for an algorithm idea, 10 points for providing the algorithm, 10 points for proving an upper (Big-Oh) bound, and 10 points for proving a lower (Big-Omega) bound. (40 points)

2) For the first part: 10 points for a proof idea, 20 points for the proof of the running time; for the second part: 5 points for explaining the idea behind the algorithm. 10 points for the details of the algorithm and its run time analysis. You will not receive any credit for the 2nd part if your algorithm has an Ω(n²) running time. (30 + 15 = 45 points)

3) If proving the statement: 5 points for explaining your ideas for the algorithm and how to prove the bound, 5 points for the details of the algorithm, and 5 points for the proof of the bound. If disproving the statement: 5 points for explaining the main ideas behind your counter example, and 10 points for providing the details. (15 points)

### Like this:

Like Loading...

*Related*

Hello. So I assume for question 1, this means we do not need a proof idea for proof of big O and big omega? Or is that just included in the proof points?

By:

Andrew Glowackion September 28, 2010at 8:45 pm

Hi Andrew. For this question, getting your ideas right for the algorithm will help lead you to the bounds that you need to prove. So although I will encourage you to be clear with explaining your justifications in proving both of those bounds, in this case we are not explicitly grading a separate “proof ideas” section of your answer for each of those.

By:

jeffon September 29, 2010at 12:49 pm