- Show that the running time of the merge-sort algorithm on an n-element sequence is O(nlogn), even when n is not a power of two.
- An algorithm that sorts key-value entries by key is said to be straggling if any time two entries ei and ej have equal keys, and ei appears before ej in the input, then the algorithm places ei after ej in the output. Describe a change to the merge-sort algorithm to make it straggling.
- Of the n! possible inputs to a given comparison-based sorting algorithm on a list of n elements, what is the absolute maximum number of inputs that could be correctly sorted with just n comparisons? Justify your answer.
- Suppose you are throwing a fancy dinner party with n guests total. When a guest walks through the front door, they check their coat in and continue to the party. However, the coat check mixes up all of the coats during dinner, so that afterward each guest receives a random coat when they prepare to leave. In other words, each guest gets their own coat with probability 1/n. What is the expected number of guests who get their correct coat?
- For each of the following recurrences, give an expression for the runtime T(n) if the recurrence can be solved with the Master Theorem. Otherwise, indicate that the Master Theorem does not apply.
T(n)=3T(n/2)+n2
T(n)=4T(n/2)+n2
T(n)=T(n/2)+2n