Question

An array A[1,2,... ,n is unimodal if its consists of an increasing sequence followed by sequence a decreasing sequence. More precisely, there exists an index k є {1,2,… ,n} such that there exists an indes . AlE]< Ali1 for all 1 i< k, and Ai]Ali 1 for all k< i< n A1,2,..,n] in O(logn) time the loop invariant (s) that your algorithm maintains and show why they lead to the correctness Give an algorithm to compute the maximum element of a unimodal input array Argue the correctness of your algorithm by presenting a proof. If you use loops, give of your algorithm. If your algorithm is defined recursively, prove its correctness by induction Finally, prove the upper bound on its running time.

Answer 1

ANSWER :

array is called unimoda iff it can be split into an increasing sequence followed by a decreasing sequence 1 3 4 57810 12 13 1410 9 6 2

ALGORITHM :

function unimodalMaximumElement(Array A, int minimum, int maximum) :

if minimum = maximum - 1:

return A[minimum]

let middleElement = ⌊(maximum + minimum) / 2⌋

if A[middleElement] < A[middleElement + 1]

return unimodalMax(A, middleElement + 1, maximum)

else:

return unimodalMax(A, minimum, middleElement + 1)

END FUNCTION

RECURRENCES FOR THE ABOVE ALGORTHM :

T(1) = Θ(1)

T(n) ≤ T(⌈n / 2⌉) + Θ(1)

COMPLEXITY :

O(log N)

22T+c 8心)-.

LOOP INVARIANTS :

We will find out the mid element of the array and compare it each time with the next element, i.e., with mid+1.

Thus, everytime loops run, we will get to an elelement which will be the required result.

WHEN we will get the element right in th middle by first attempt, then the UPPER BOUND will be :

T(1) = Θ(1)

AFTER THAT, loop variants offers us following recurrence upper bound on the array A :

T(n) ≤ T(⌈n / 2⌉) + Θ(1)

THUS MAKING THE TIME COMPLEXITY TO O(log N).

OR

ANS:

Please let me know in case of any issue.

We can modify the standard Binary Search algorithm for the given type of arrays.
i) If the mid element is greater than both of its adjacent elements, then mid is the maximum.
ii) If mid element is greater than its next element and smaller than the previous element then maximum lies on left side of mid. Example array: {3, 50, 10, 9, 7, 6}
iii) If mid element is smaller than its next element and greater than the previous element then maximum lies on right side of mid. Example array: {2, 4, 6, 8, 10, 3, 1}

int findMaximum(int arr[], int low, int high)
{

/* Base Case: Only one element is present in arr[low..high]*/
if (low == high)
return arr[low];

/* If there are two elements and first is greater then
the first element is maximum */
if ((high == low + 1) && arr[low] >= arr[high])
return arr[low];

/* If there are two elements and second is greater then
the second element is maximum */
if ((high == low + 1) && arr[low] < arr[high])
return arr[high];

int mid = (low + high)/2; /*low + (high - low)/2;*/

/* If we reach a point where arr[mid] is greater than both of
its adjacent elements arr[mid-1] and arr[mid+1], then arr[mid]
is the maximum element*/
if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])
return arr[mid];

/* If arr[mid] is greater than the next element and smaller than the previous
element then maximum lies on left side of mid */
if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
return findMaximum(arr, low, mid-1);
else // when arr[mid] is greater than arr[mid-1] and smaller than arr[mid+1]
return findMaximum(arr, mid + 1, high);
}

Time Complexity: O(Logn)