Write clearly.
Write your name and section clearly on the top of the first page.
Scan/photograph clearly.
If we can't read it, we will grade it as incorrect.
After you finish your answers, scan or carefully photograph your answer sheets
and create a single PDF with those images to upload
to the ELMS entry.
You cannot e-mail them to me.
We may only grade some subset of these, but you are expected to do them all.
Use the techniques from class as you solve these homework problems.
(1) Assuming that you can find the median of a 6-element list in B steps
and that this is defined as returning the 3rd smallest value:
(a) Determine the Θ of the worst-case runtime of the
"Median of Medians" algorithm assuming it uses "6"
rather than "3" or "5" as we had seen in class. This
means that you look at the recurrence always assuming
the biggest possible bucket in which to recurse.
Show your work.
(b) Once you have that asymptotic class, use constructive
induction to construct the best Big-O constant C that
you can for that high-order term. If B is a part of that
constant, keep the B in the final answer. Again, show your
work.
REMINDER: To make the algebra nicer, and to reflect that you
might need to compare the pivot to itself when you do the
partitioning to make the code easier, you should say that
partitioning has a cost of exactly n rather than n-1.
(2) For this problem, do a careful recursion tree for Quicksort, counting
comparisons, but where you assume that the pivot that gets selected is
ALWAYS the median, and where you do not send the pivot into either
recursive call after partitioning.
Asssume that picking of the pivot is "free" for this analysis.
Solve the summation carefully, keeping lower order terms in mind this time.
You can assume a power-of-2 (or something similar) for the list's initial
size to avoid floor/ceiling issues if you'd like.
I would suggest you do a trace by hand using a small input size (perhaps
n=15 or n=16) to get a feel for the pattern.
(3) We have a potential sorting algorithm as follows:
Step 1: If we only have two elements, sort them by comparing
them to each other and swapping if needed.
Step 2: Recursively sort the first 2/3rds of the list.
Step 3: Recursively sort the last 2/3rds of the list.
Step 4: Recursively sort the first 2/3rds of the list.
Assume "ceilings" on all fractions.
(a) What is the very worst this algorithm could end up with as
its worst-case runtime in terms of comparisons?
Hint
(b) Does this algorithm always lead to an ordered list? If it does,
describe why you think this and maybe give a short input trace
that supports it. If it does not, then give a short input for
which the output will be incorrect.