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

Expert Solution

1. The main idea behind the algorithm is to scan the array in the linear order and find the maximum element and make the second largest element as the previous value of the maximum value. This basically means that while traversing through the list, we need to compare the current element with the maximum value and if we find a new maximum then we need to make the second-largest value to the previous value of the maximum and update the maximum value.

2. Psuedo-Code

function findFirSecLargest(A):
   maximum = -1;
   secondmaximum = -1;
   for i in A:
       if i > maximum:
           secondmaximum = maximum
           maximum = i
   print(maximum)
   print(secondmaximum)

3. So the total number of comparisons done in the above pseudocode/Algorithm is just n, in which we are comparing each element of the array with the current maximum value.

Friend, That was a nice question to answer
If you have any doubts in understanding do let me know in the comment section. I will be happy to help you further.
Thanks

venereology answered 3 months ago

Given an array of n numbers, not necessarily in sorted order, we wish to find: (i)...

Given an array of n numbers, not necessarily in sorted order, we wish to find: (i) the range (max - min) and (ii) the interquartile range (IQR) of the numbers. IQR is defined as the difference between the number at the 25% percentile and the number at the 75% percentile. What is the exact number of comparisons needed for computing the range and why? Using any algorithm from the chapters of the textbook covered so far as a subroutine, give...

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

Consider the following pseudocode for insertion-sort algorithm. The algorithm sorts an arbitrary array A[0..n − 1]...

Consider the following pseudocode for insertion-sort algorithm. The algorithm sorts an arbitrary array A[0..n − 1] of n elements. void ISORT (dtype A[ ], int n) { int i, j; for i = 1 to n – 1 { //Insert A[i] into the sorted part A[0..i – 1] j = i; while (j > 0 and A[j] < A[j – 1]) { SWAP (A[j], A[j – 1]); j = j – 1 } }...

please write in c++ Algorithm Design problem: Counting inversions: given an array of n integers, find...

please write in c++ Algorithm Design problem: Counting inversions: given an array of n integers, find out the total number of inversions in the given sequence. For example, for the sequence of 2, 4, 1, 3, 5, there are three inversions (2,1), (4,1), and (4,3). Give a brute-force algorithm with running time of O(n^2). Using the technique of divide-and-conquer, design an algorithm with running time of O(nlog n).

Given an array A of n integers, describe an O(n log n) algorithm to decide if...

Given an array A of n integers, describe an O(n log n) algorithm to decide if the elements of A are all distinct. Why does your algorithm run in O(n log n) time?

Following is the algorithm of Quicksort for sorting an array of integers in ascending order. Partition(numbers,...

Following is the algorithm of Quicksort for sorting an array of integers in ascending order. Partition(numbers, lowIndex, highIndex) { midpoint = lowIndex + (highIndex - lowIndex) / 2 pivot = numbers[midpoint] done = false while (!done) { while (numbers[lowIndex] < pivot) lowIndex++ while (pivot < numbers[highIndex]) highIndex-- if (lowIndex >= highIndex) { done = true } else { temp = numbers[lowIndex] numbers[lowIndex] = numbers[highIndex] numbers[highIndex] = temp lowIndex++ highIndex-- } } return highIndex } Quicksort(numbers, lowIndex, highIndex) { if (lowIndex...

Let A be an integer array of length n. Design a divide and conquer algorithm (description...

Let A be an integer array of length n. Design a divide and conquer algorithm (description and pseudo code) to find the index of an element of the minimum value in the array. If there are several such elements, your algorithm must return the index of the rightmost element. For instance, if A = {0,2,4,5,2,0,3,10}, then the algorithm should return 5, which is the index of the second 0.

algorithm binarySearch input bottom, top: a number a: array a[0] to a[n-1] of numbers x: a...

algorithm binarySearch input bottom, top: a number a: array a[0] to a[n-1] of numbers x: a number output result: true if x in a false otherwise Sideeffect NA Plan if (top < bottom) result := false else // get the middle of the array (refining) middle := (top - bottom)/2 + bottom (refining by +1 or -1 or integer division …) // example what is midpoint between 6 and 8 // (8-6)/2 = 1 we need to add 6 to...

Project: Given an array numbers. We define a running sum of an array as runningSum[i] =...

Project: Given an array numbers. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]). Return the running sum of numbers. Example: Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4]. You need to do: Create a class called RunningSumArray to perform the main method. Create a class called ArrayOperationto hold the actions for array. In this project, you will need 4methods: 1. Public static Int[] getArray() --- inside ArrayOperationclass,...

Question