nates of n 4. (20 pts) Let X be an array of integers that stores the x Pr on the
ID: 3594959 • Letter: N
Question
nates of n 4. (20 pts) Let X be an array of integers that stores the x Pr on the x-axis of a Cartesian plane, where Xji] stores the x-coordinate of p. We want to determine if there are two points p, and p, where the x-coordinate of their midpoint which is defined as (Xi + X[])/2, equals a given value d> 0. (10 pts) Write an O(n2)-time algorithm to solve the above problem. Explain why your algorithm runs in O(n2) time. (a) (b) (10 pts) Write an O(n log n)-time algorithm to solve the same problem as in (a) Explain why your algorithm runs in O(n log n) tiExplanation / Answer
this is a simple problem
1.
to get n2 complexity , two for loops should be used .
We need to get distance between each pair of points in the plane , then check it with the given distance.
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i!=j)// if i==j then we are taking same points
{
mid_p=(x[i]+x[j])/2;
if(mid_p<0)
{
mid_p= -1*mid_p;//in case of mid point in negative
}
if(mid_p==given_distance)
{
print x[i] and x[j] as the results
exit the program
}
}
}//end for loop with variable i
}//end for loop with variable j
print "Not any pair "
exit the program
Here are two nested for loops so complexity = O(n2)
2.
to get nlogn , use array x with merge sort -
here is the algorithm for merge sort -
MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
And this is the code for merge sort -
#include<stdio.h>
#include<stdlib.h>
void merge(int a[],int l,int m,int h);
void sort(int a[],int l,int h);
void sort(int a[],int l,int h)
{
if(l<h)//check if we should go forward or not may be there is only one element
{
int m=(l+(l-h))/2;//(l+h)/2 also working and it's same thing only but it removes overflow
sort(a,l,m);//to sort till middle
sort(a,m+1,h);//to sort after middle
merge(a,l,m,h);//merge all
}
}
void merge(int a[],int l,int m,int h)
{
int i=0,j=0,k=l;
int n1;
int n2;
n1=m-l+1;
n2=h-m;
int a1[n1],a2[n2];
for(i=0;i<n1;i++)
{
a1[i]=a[i+l];
}
for(j=0;j<n2;j++)
{
a2[j]=a[j+m+1];
}
i=0,j=0;
while(i<n1&&j<n2)
{
if(a1[i]<a2[j])
{
a[k]=a1[i];;
i++;
}
else
{
a[k]=a2[j];
j++;
}
k++;
}
while(i<n1)
{
a[k]=a1[i];
k++;
i++;
}
while(j<n2)
{
a[k]=a2[j];
k++;
j++;
}
}
int main()
{
int n=10,i;//range=10
int a[10]={5,4,3,2,1,7,8,9,0,6};//array
sort(a,0,n-1);//calling sort function
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf(" ");
return 0;
}
//now we can apply binary search type algorithm that will take logn time to get mid point -
so algorithm is-
int binarySearch(int x[], int l, int r, int given_distance)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle itself
if ((x[i]+x[j])/2 == given_distance)
{
print x[i] and x[j] as the results
}
// If midpoint is smaller than given distance , then it can only be present
// in left subarray
if ((x[i]+x[j])/2 > given_distance)
return binarySearch(x, l, mid-1, given_distance);
// Else the midpoint can only be present in right subarray
return binarySearch(x, mid+1, r, given_distance);
}
// We reach here when pair is not present in array
return -1;
}
so overall complexity of the program in second solution is nlogn because of merge sort and logn because of binary search type algrithm , so overall complexity = nlogn
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.