Programming help please! (in java) 1.In all of the following sub-questions, give
ID: 3678653 • Letter: P
Question
Programming help please! (in java)
1.In all of the following sub-questions, give an algorithm in recursive form and show its running time using the Master Theorem or just by solving the recurrence in the simpler cases.
A) Describe a (n)-time algorithm that, given a set S of n integers, determines which two elements in S have the largest sum.
B) Describe a (n)-time algorithm that, given a set S of n integers, determines which two elements in S have the largest difference.
C) Describe a (n)-time algorithm that, given a set S of n integers, determines which two elements in S have the smallest sum.
D) Describe a (n lg n)-time algorithm that, given a set S of n integers, determines which two elements in S have the smallest difference.
E) Describe a (n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x
Explanation / Answer
Can help you with E)
E)
void sum(int a[],int n,int S)
{
mergesort(a,0,n-1);
int i=0,j=n-1;
while(i<j)
{
if(a[i]+a[j]>S)
j--;
else if(a[i]+a[j]<S)
i++;
else
{
printf("YES");
break;
}
}
if(i==j)
printf("NO");
}
int bisearch(int a[],int start,int end,int key)
{
int middle=0;
while(start<end)
{
middle=(start+end)/2;
if(key<a[middle])
end=middle-1;
else if(key>a[middle])
start=middle+1;
else
return 1;
}
return 0;
}
void sumbsearch(int a[],int n,int S)
{
mergesort(a,0,n-1);
int i=0,tmp=0;
for(i=0;i<n-1;i++)
{
tmp=S-a[i];
if(bisearch(a,i+1,n-1,tmp)==1)
{
printf("YES");
break;
}
}
if(i==n-1)
printf("NO");
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.