Posted by: Jesse | September 19, 2011

1. Not turned in.

2. (40 pts)
(16 pts) for the correct order: 2 pts for each correctly ordered function (relative to its neighbors) and 4 more points for having them all in order.
(24 pts) for explaining correctness: 4 pts for each.

3. (45 pts)
(30 pts) for O(f(n)):  10 points for determining a function f(n) for which the running time is O(f(n)), 10 points for a proof idea, and 10 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.

4. (15 pts)
(4 pts) for explaining the idea behind your algorithm or a reduction to a familiar problem
(3 pts) for providing the specific details of the algorithm or the reduction
(4 pts) for a proof idea that you can always achieve a valid switching
(4 pts) for providing the proof