Posted by: jiunjiewang | September 22, 2012

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