Plan
School of Computing and Information Systems COMP90038 Algorithms and Complexity Tutorial Week 7
3–7 September 2018
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 recur- rences. 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
47. When analysing quicksort in the lecture, we noticed that an already sorted array is a worst- case input. Is that still true if we use median-of three pivot selection?
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 n log n 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 .