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

(c) Now consider the multi-slumped generalization, in which the array contains k local minima, i.e., it contains k subarrays, each of which is itself a slumped 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 local minimum is closer than n/3 positions to the middle of the array, and that the joining point of the two singly-slumped subarrays lays in the middle third of the array. Now write an algorithm that tests A for identical adjacent values in sublinear time. Prove that your algorithm is correct, give a recurrence relation for its running time, and solve for its asymptotic behavior.

3. (30 pts) Professor Flitwick asks you to help him with some arrays that are slumped. An array A is slumped if A1.i has the property that, for some C > 0, Alj +1A-C for 1 j