Plan
If you skipped important questions in previous weeks, or if you have doubts about how to approach particular types of questions,now is the time to catch up, and to ask those questions in your tutorial.
The exercises
42. Trace how QuickSelect finds the median of 39, 23, 12, 77, 48, 61, 55.
43. We can use QuickSelect to find the smallest element of an unsorted array. How does it compare to the more obvious way of solving the problem, namely scanning through the array and maintaining a variable min that holds the smallest element found so far?
44. Apply mergesort to the list S, O, R, T, X, A, M, P, L, E.
45. Apply quicksort (with Hoare partitioning) to the list S, O, R, T, X, A, M, P, L, E.
46. Use the Master Theorem to find the order of growth for the solutions to the following recurrences. In each case, assume T(1) = 1, and that the recurrence holds for all n > 1.
(a) T(n) = 4T(n/2) + n
(b) T(n) = 4T(n/2) + n2 (c) T(n) = 4T(n/2) + n3
48. Let A[0..n − 1] be an array of n integers. A pair (A[i],A[j]) is an inversion if i < j but A[i] > A[j], that is, A[i] and A[j] are out of order. Design an efficient algorithm to count the number of inversions in A.
Hint: Try to adapt mergesort for this problem, so as to achieve an nlogn algorithm.
49. Let T be defined recursively as follows:
T(1) = 1
T(n) = T(n − 1) + n/2 n > 1
The division is exact division, so T(n) is a rational, but not necessarily natural, number. For example, T(3) = 7/2. Use telescoping to find a closed form definition of T.
