Design a linear time divide and conquer algorithm to compute the problem. 2. (20
ID: 3915400 • Letter: D
Question
Design a linear time divide and conquer algorithm to compute the problem.
2. (20 pts) Consider the following problem A[1 to n] of distinct integers Input: array , and integerx Output: the rank of the integer closest to x in A Here the rank means the minimum rank, i.e., the rank of the smallest in A is 1, that of the 2n smallest is 2, etc. Consequently if the element closest to x is the kth smallest of A, the output is k. For example, if All to 4H 8, 1, 5, 20) and x-4, the output is 2 because the closest to 4 is 5, having rank 2. If xa, the output can be either 1 or 2. Design a linear time divide and conquer algorithm to compute the problem. Write all of: o your basic method in 3-10 lines, o complete pseudo code, o proof of the algorithm correctness, and o that of the running time O(n) with the running time recurrence. Make your answers succinct but include everything necessary to reason the aboveExplanation / Answer
Devide the array into sub parts recurssivly each time two parts.
when subarray have the single element then compare with x value.
If element is less than x then return 1 else return 0.
At the same time we find out the nearest minimum value and nearest max value of x.
return vlue is added to the count . After successful completion of recurrence
function we have how many elements are less than x.
If x is exist in the array then rank is count+1.
if x is not there in x the nearest element rank is assigned to x.
::::::Psudocode:::::::
array[1...n]
start_index=1;
end_index=n;
input : x
Rank_X (array[] ,int start_index, int end_index, int x)
{
if(start_index < end_index)
{
mid = (start_index + end_index)/2
rank = Rank_X(array,start_index, mid, x) + Rank_X(array,mid+1, end_index, x);
}
else
{
if(arr[start_index]<x)
return 1;
else
return 0;
}
}
This is the main functionlity in this algorithm .
For every case see the below program in c.
::::::::Proof by execution of program:::::::
#include <stdio.h>
int rank=1;
int min,max;
int Rank_X(int *arr,int p,int r,int x)
{
if(p<r)
{
int mid = (p+r)/2;
rank = Rank_X(arr,p,mid,x)+Rank_X(arr,mid+1,r,x);
return rank;
}
else{
if(arr[p]<x){
if(arr[p]>min)
min=arr[p];
return 1;
}
else if(arr[p]==x)
{
min=x;
max=x;
return 0;
}
else{
if(max==-1)
max=arr[p];
if(arr[p]<max)
max=arr[p];
return 0;
}
}
}
int main(void)
{
int n,i,x;
printf("Enter array size:");
scanf("%d",&n);
int arr[n];
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
printf("Enter x:");
scanf("%d",&x);
min=-1;
max=-1;
rank = Rank_X(arr,0,n-1,x);
((x-min)<(max-x))? printf("Rank %d: ",rank): printf("Rank %d: ",rank+1);
}
Input::::
Enter array size : 5
2
3
1
6
4
Enter x:3
output::::
Rank :3
..............................................................................
Recurrence relation :
T(n) = 2T(n/2)+c where n>1
Otherwise
= 1
time complexity :
by masters theorem it is O(n).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.