1. Engineering
  2. Computer Science
  3. 3 30 pts professor flitwick asks you to help him...

Question: 3 30 pts professor flitwick asks you to help him...

Question details

3. (30 pts) Professor Flitwick asks you to help him with some arrays that are slumped. An array A is slumped if A[1..i] has the property that, for some C > 0, A[j + 1] = A[j]−C for 1 ≤ j < i, and A[i..n] has the property that, for some D > 0 where C 6= D, A[j + 1] = A[j] + D for i ≤ j < n. Using his wand, Flitwick writes the following slumped array on the board A = [7, 3, −1, −5, 0, 10, 15, 20, 25], as an example. i is just some number, you don't need to know the value of i to answer this question.

(a) Flitwick found that one of his slumped arrays had an identical adjacent value (i.e., A[j] = A[j +1]) and no longer trusts any of his slumped arrays. Write a recursive algorithm that takes asymptotically sub-linear time to ensure that there are no identical adjacent elements in A.

(b) Prove that your algorithm is correct. (Hint: prove that your algorithm’s 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.

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution