An array A of n distinct numbers are said to be unimodal if there exists an...

An array A of n distinct numbers are said to be unimodal if there exists an index k, 1 ≤ k ≤ n, such that A[1] < A[2] < · · · < A[k − 1] < A[k] and A[k] > A[k + 1] > · · · > A[n]. In other words, A has a unique peak and are monotone on both sides of the peak. Design an efficient algorithm that finds the peak in a unimodal array of size n.

Expert Solution

Answer : Given data

* Unimodal if there exists an index k, 1 ≤ k ≤ n, such that A[1] < A[2] < · · · < A[k − 1] < A[k] and A[k] > A[k + 1] > · · · > A[n].

public int findPeak(int[] arr, int low, int high){
       if(low == high - 1){
           return arr[low];
       }

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

       if(arr[mid] < arr[mid + 1]){
           return findPeak(arr, mid + 1, high);
       } else{
           return findPeak(arr, low, mid - 1);
       }
   }

*You can call this method from the main method as follows : findPeak(arr, 0, n - 1)

*where n is the length of the array.

*What we are essentially doing is the reducing our search space in the array to half after each recursive call until we meet our base condition.

______________THE END__________________

venereology answered 5 months ago

Given an array A of n distinct real numbers, we say that a pair of numbers...

Given an array A of n distinct real numbers, we say that a pair of numbers i, j ∈ {0, . . . , n−1} form an inversion of A if i < j and A[i] > A[j]. Let inv(A) = {(i, j) | i < j and A[i] > A[j]}. Answer the following: (a) How small can the number of inversions be? Give an example of an array of length n with the smallest possible number of inversions. (b)...

Given an array A of n distinct numbers, we say that a pair of numbers i,...

Given an array A of n distinct numbers, we say that a pair of numbers i, j ∈ {0, . . . , n − 1} form an inversion of A if i < j and A[i] > A[j]. Let inv(A) = {(i, j) | i < j and A[i] > A[j]}. Define the Inversion problem as follows: • Input: an array A consisting of distinct numbers. • Output: the number of inversions of A, i.e. |inv(A)|. Answer the following:...

Given an array A[1..n], with distinct values and k with 1 ≤ k ≤ n. We...

Given an array A[1..n], with distinct values and k with 1 ≤ k ≤ n. We want to return the k smallest element of A[1.....n], in non-decreasing order. For example: A = [5, 4, 6, 2, 10] and k = 4, the algorithm returns [2, 4, 5, 6]. There are at least the following four approaches: a. heapify A and then extract k elements one by one b. sort the array (e.g. using MergeSort or HeapSort) and then read the...

The following algorithm returns true if the n items in an array are all distinct, i.e.,...

The following algorithm returns true if the n items in an array are all distinct, i.e., if no two items are equal to each other, otherwise it returns false. 1 ALGORITHM UniqueElements(A[1..n]) 2 // Determine whether all the elements in an array are distinct 3 // Input: Array A[1..n] 4 // Output: “true” if all elements of A are distinct, “false” otherwise 5 for i ← 1 to n – 1 do 6 for j ← i + 1 to...

5. Suppose you are given an n-element array containing distinct integers that are listed in increasing...

5. Suppose you are given an n-element array containing distinct integers that are listed in increasing order. Given a number k, describe a recursive algorithm to find two integers in A that sum to k, if such a pair exists. What is the running time of your algorithm? Java Language....

Suppose you are given an n-element array containing distinct integers that are listed in increasing order....

Suppose you are given an n-element array containing distinct integers that are listed in increasing order. Given a number k, describe a recursive algorithm to find two integers in A that sum to k, if such a pair exists. What is the running time of your algorithm?

5. Let n = 60, not a product of distinct prime numbers. Let Bn= the set...

5. Let n = 60, not a product of distinct prime numbers. Let Bn= the set of all positive divisors of n. Define addition and multiplication to be lcm and gcd as well. Now show that Bn cannot consist of a Boolean algebra under those two operators. Hint: Find the 0 and 1 elements first. Now find an element of Bn whose complement cannot be found to satisfy both equalities, no matter how we define the complement operator.

give an algorithm where given as input an array A[1...n] withthe following property. There exists...

give an algorithm where given as input an array A[1...n] with the following property. There exists an index I such that if we append A[1...i−1] after A[i...n], we get an array in sorted increasing order. For simplicity you can assume that n is a power of 2.Give an efficient algorithm that returns the smallest element in A. Analyze the time complexity of your algorithm.Hint: you may want to compare A[1] and A[n/2].

Given a minimum unimodal array of integers, run the binary search algorithm to find the minimum...

Given a minimum unimodal array of integers, run the binary search algorithm to find the minimum element. You need to show the initial and the iteration-level values of the left index, right index and middle index as well as your decisions to reduce the search space in each iteration. 42 39 2 6 9 16 20 28 31 34

Consider sorting n numbers stored in array A by first finding the smallest element of A...

Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A and exchange it with A[2]. Continue in this manner for the first n-1 elements of A. a) (10 points) This algorithm is known as the selection sort. Write the pseudo code for this algorithm. b) (10 points) What loop invariant does this algorithm maintain? Note: You do not...

Question