32. You are given an array A of n distinct integers (in not arranged in any part
ID: 3721281 • Letter: 3
Question
32. You are given an array A of n distinct integers (in not arranged in any particular order. The objective is t and the second largest of these integers if ra 2. For the sake of simplicity, you can nssume that Warning: Don't sort the whole array. dexed t I through n) which are o determine the Iurgest n integers. Observe that the problem in trivial of two. n is a power (a) Develop an algorithm based on the divide and conquer principle to do so. Present your idea in the form of a pseudocode. Provide brief explanation in English as well. (4 Pts.) of your algorithm. State both the recurrence relation and the base condi- tion for it. Assume that the comparison of two integers from the array is the only time consuming operation. Time spent doing anything else can be ignored. (3 Pts.) (b) Develop a recurrence relation for the running time (worst case complexity)Explanation / Answer
For Part
a.) We First divide the array into two parts and then find the largest two elements in each half. And the end, we need to return the largest two out of four because each half return s two elements.
The Base Case is when the array contains Zero, one or Two elements.
//Pseudo Code.
struct Result {
int max1, max2;
};
Result OneTwoMax(int A[], int l, int r) {
//Base Case
Result res;
res.max1 = A[l];
res.max2 = A[l];
//If array has only one element
if(l == r)
return res;
//If array has only two elements
if(r - l == 1) {
//If right element is greater than the left element
if(A[r] >= A[l]) {
res.max1 = A[r];
res.max2 = A[l];
}
else
{
res.max1 = A[l];
res.max2 = A[r];
}
return res;
}
//Find Middle element
int mid = (l + r) / 2;
//Recursively find largest two elements in each half
Result lres = FirstSecondMax(A, l, mid);
Result rres = FirstSecondMax(A, mid + 1, r);
//So far we got 4 max values, 2 on each half
//so we need to merge them and take out only
//two. Basically you compare the largest element
//on the right side with the largest element on
//the left side and take the greater one as the
//result first max. In case the taken one was the
//first max on the right then you need to compare
//the second max on the right with the first max
//on the left. If it is greater then you take it
//as the second max otherwise you take the first
//max on the left as the result second max. You
//do the same if the taken one was on the left.
//First max on the right is greater than
//first max on the left
if (rres.max1 >= lres.max1)
{
//Take the first max on the right
res.max1 = rres.max1;
//Compare second max on the right with
//first max on the left
if (rres.max2 >= lres.max1)
{
res.max2 = rres.max2;
}
else
{
res.max2 = lres.max1;
}
}
//First max on the left is greater than
//first max on the right
else
{
//Take the first max on the left
res.max1 = lres.max1;
//Compare second max on the left with
//first max on the right
if (lres.max2 >= rres.max1)
{
res.max2 = lres.max2;
}
else
{
res.max2 = rres.max1;
}
}
return res;
}
//Code Ends.
For Part b.)
Given N elements, recursively calculate the largest and next-largest for the first N/2 and second N/2 of the elements. This provides four values; using the naming convention introduced above, they are: LM1, LM2, RM1, RM2.
Compare LM1 to RM1. The larger one is the largest overall value. Suppose it’s LM1. Then the next-largest value is max( LM2, RM1 ). In the case where the largest is RM1 then symmetrically the next-largest is max( LM1, RM2 ). So at each level of the recursion we do two comparisons.
Thus, the recurrence is T(n) = 2T(n/2) + 2
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.