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)
Advertisements

Responses

  1. 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?

    • 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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: