Posted by: jiunjiewang | September 22, 2012

HW3 Grading Rubric

1. (40 pts)
(25 pts) for O(f(n)):  10 points for determining a function f(n) for which the running time is O(f(n)), 8 points for a proof idea, and 7 points for a proof of that bound.
(15 pts) for Ω(g(n)):  5 points for determining a function g(n) for which the running time is Ω(g(n)), 5 points for a proof idea, and 5 points for a proof of that bound. A tight bound for the second part (i.e. so your g(n) is Θ(f(n)) ) is required to receive full credit.

2. (45 pts)
(14 pts) for proving big-O.  7 pts for the proof idea.  7 pts for the proof
(16 pts) for proving big-Ω.  8 pts for the proof idea.  8 pts for the proof
*If you prove big-Θ directly, you will receive 15 pts for the proof idea and 15 pts for the proof.
(7 pts) for explaining the idea behind the new algorithm
(5 pts) for the details of the algorithm
(3 pts) for the run time analysis
*You will not receive any credit for the 2nd part if your algorithm has an Ω(n²) running time.

3. (15 pts)
(7 pts) for part (a).  3 pts for the algorithm idea.  2 pts for the algorithm details.  2 pts for a proof that the runtime is faster than O(n).
(8 pts) for part (b).  4 pts for the algorithm idea.  2 pts for the algorithm details.  2 pts for the proof of runtime.  (The runtime must get asymptotically faster as k increases to get full credit on part (b)).

Advertisements

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: