Consider the following algorithm (don’t worry about what it does – we’re only interested in the running time).
Something(A) // A is a problem of size n
if n == 1
return A[1]
else
(A1,A2,A3) = split(A) // linear time - each Ai result has size n/2
v1 = Something(A1)
v2 = Something(A2)
v3 = Something(A3)
return max(v1, v2, v3)Derive a recurrence describing the running time of this algorithm. It doesn’t have to be a detailed analysis, but it does need some explanation (don’t just write formulas – explain where they come from).
Solve this recurrence using the master theorem, showing your work (this includes verifying any conditions that must be met to apply the relevant case of the theorem).
Do a manual execution of algorithm \(\texttt{Find-Maximum-Subarray}\) from the book (page 72), using as input the 8-element array [6, -7, 5, -1, -2, 6, 1, -2]. Show every step, tracing down into recursive calls as well as the calls to \(\texttt{Find-Max-Crossing-Subarray}\). At the end, clearly mark your result (in other words: what is the maximum subarray?).
Solve the recurrences below using the master theorem if possible, showing your work. One of these is not solvable by the basic master theorem (as stated on page 94 of the textbook) – for that one, explain why we can’t use the master theorem.
\(T(n)=4T(n/2)+n\)
\(T(n)=3T(n/3)+n\lg n\)
\(T(n)=4T(n/2)+n^2\)
\(T(n)=9T(n/3)+n^3\lg n\)
When the pivot element in chosen as the last element in your subarray (as in the code on page 171), the worst-case input is simple: already-sorted input gives worst case performance, since the pivot is always the maximum value in the subarray. What if we always picked the middle element as the pivot? We can do this by replacing line 1 in \(\texttt{Randomized-Partition}\) on page 179 with this line: \[ 1\ \ \ \ \ \ i = \left\lfloor (p+r)/2 \right\rfloor \] Note that this removes the randomization, so \(\texttt{Randomized-Partition}\) isn’t an accurate name any more, but it is still a valid algorithm. This algorithm has a worst-case running time of \(\Theta(n^2)\), just like the earlier algorithm, but finding the worst-case input is more difficult.
Give an ordering of the integers 1 through 15 that results worst-case performance of this algorithm. Explain why your input is a worst-case input.
Hacker Harry is trying to implement \(\texttt{Quicksort}\) from the pseudocode in the textbook (page 171). However, he makes a mistake when entering Line 3 and instead calls \(\texttt{Quicksort}(A, p, q)\) (note the change in the final parameter).
What is the consequence of this mistake (on correctness or running time) when \(\texttt{Quicksort}\) is called with an array that is already in sorted order?
What is the consequence of this mistake (on correctness or running time) when \(\texttt{Quicksort}\) is called with an array that is filled with \(n\) copies of the same value?
Programming Challenges – given on a separate page.