In the last homework, for problem 3 you wrote pseudocode for recursive binary search (with the array passed by reference) and derived a recurrence describing the worst-case running time. The correct recurrence for this is \(T(n)=T(n/2)+c\); solve this using the master theorem, showing your work including the verification of conditions for using a particular case of the master theorem.
In the last homework, problem 4 asked about what would happen if the array were passed by value instead of by reference. The recurrence you should have gotten for that one was \(T(n)=T(n/2)+c\cdot n\). Solve this, showing your work as in the last problem.
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^3\)
\(T(n)=9T(n/3)+n^2\lg n\)
\(T(n)=8T(n/2)+n^2\lg n\)
\(T(n)=16T(n/2)+n^4\)
Do a manual execution of algorithm \(\texttt{Find-Maximum-Subarray}\) from the book (page 72), using as input the 8-element array [-1, 5, -2, 6, 3, -7, -6, 5]. 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?).
In the closest pair algorithm from Section 33.4 (and that we discussed in class), the divide-and-conquer continues until \(n\leq 3\). Why is the base case \(n\leq 3\)? Or more specifically, would there be a problem if you kept doing recursion when \(n=3\) and only stopped when \(n\leq 2\)?
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.