Zookal Homework Help

Homework Help

  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] has the property that, for some C> 0, Alj 1A]-C for 1 j < i, and A[i..n] has the property that, for some D> 0 where C D, Ali + 1] = A1八+ D for i < j < n. Using his wand. Flatwick writes the following slumped array on the board A [7,3,-1,-5,0, 10, 15,20, 25], as an erample. as an example (a) Flitwick found that one of his slumped arrays had an identical adjacent value (i.e., Aj] Alj+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 algorithms correct- ness follows from the correctness of another correct algorithm we already know.)(c) Now consider the multi-slumped ge neralization, in which the array contains k local minima, i.e., it contains k subarrays, each of which is tself a slumped array. Let k 2 and prove that your algorithm can fail on such an input(d) Suppose that k2 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