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 7 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...

Python - You are given a sorted (from smallest to largest) array A of n distinct...

Python - You are given a sorted (from smallest to largest) array A of n distinct integers which can be positive, negative or zero. Design the fastest algorithm you can for deciding if there is an index i such that A[i] = i.

Let A[1..n] be an array of distinct positive integers, and let t be a positive integer....

Let A[1..n] be an array of distinct positive integers, and let t be a positive integer. (a) Assuming that A is sorted, show that in O(n) time it can be decided if A contains two distinct elements x and y such that x + y = t. (b) Use part (a) to show that the following problem, re- ferred to as the 3-Sum problem, can be solved in O(n2) time: 3-Sum Given an array A[1..n] of distinct positive integers, and...

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.

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?

We are given an array of n numbers A in an arbitrary order. Design an algorithm...

We are given an array of n numbers A in an arbitrary order. Design an algorithm to find the largest and second largest number in A using at most 3/2n -2 comparisons. (i) describe the idea behind your algorithm in English (3 points); (ii) provide pseudocode (5 points); (iii) analyze the number of comparisons used in your algorithm (2 points).

Question