Consider a valleyed array A[1, 2, , n] with the property that the subar- ray A[1..i] has the property that A[j] > A[j + 1] for 1 j < i, and the subar- ray A[i..n] has the property that A[j] < A[j + 1] for i j < n. For example, A = [16,15,10,9,7,3,6,8,17,23] is a valleyed array.

(a) Write a recursive algorithm that takes asymptotically sub-linear time to find the minimum element of A.

(b) Prove that your algorithm is correct. (Hint: prove that your algorithms correct- ness follows from the correctness of another correct algorithm we already know.)

(c) Now consider the multi-valleyed generalization, in which the array contains k valleys, i.e., it contains k subarrays, each of which is itself a valleyed array. Let k = 2 and prove that your algorithm can fail on such an input.

(d) Suppose that k = 2 and we can guarantee that neither valley is closer than n/4 positions to the middle of the array, and that the joining point of the two singly-valleyed subarrays lays in the middle half of the array. Now write an algorithm that returns the minimum element of A in sublinear time. Prove that your algorithm is correct, give a recurrence relation for its running time, and solve for its asymptotic behavior.