- #1
evinda
Gold Member
MHB
- 3,836
- 0
Hello! (Wave)
Consider two sets $D=\{ d_1, d_2, \dots, d_n\}$ and $E=\{ e_1, e_2, \dots, e_m \}$ and consider an other variable $K \geq 0$.
Show that we can answer in time $O((n+m) \lg (n+m))$ the following question:
Is there is a pair of numbers $a,b$ where $a \in D, b \in E$ such that $|a-b| \leq K$?
The algorithm should answer the above question with <<YES>> or <<NO>>.
Describe the algorithm, show its correctness and show that its time complexity is $O((n+m) \lg (n+m))$.I thought that we could do it like that:
We create a new array $A$ that contains both the elements of $D$ and $E$.
Then $A=\{ d_1, d_2, \dots d_n, e_1, e_2, \dots, e_n \}$.
We sort the array $A$.
Then we only look at the differences of the adjacent elements, so at $|d_1-d_2|, |d_2-d_3|$ and so on.. We can do it like that because the array is sorted and if the difference of the adjacent elements isn't less than $D$, neither the difference of the first of these elements with an other element will be.
I wrote this algorithm:
Could you tell me if my idea is right? (Thinking)
Consider two sets $D=\{ d_1, d_2, \dots, d_n\}$ and $E=\{ e_1, e_2, \dots, e_m \}$ and consider an other variable $K \geq 0$.
Show that we can answer in time $O((n+m) \lg (n+m))$ the following question:
Is there is a pair of numbers $a,b$ where $a \in D, b \in E$ such that $|a-b| \leq K$?
The algorithm should answer the above question with <<YES>> or <<NO>>.
Describe the algorithm, show its correctness and show that its time complexity is $O((n+m) \lg (n+m))$.I thought that we could do it like that:
We create a new array $A$ that contains both the elements of $D$ and $E$.
Then $A=\{ d_1, d_2, \dots d_n, e_1, e_2, \dots, e_n \}$.
We sort the array $A$.
Then we only look at the differences of the adjacent elements, so at $|d_1-d_2|, |d_2-d_3|$ and so on.. We can do it like that because the array is sorted and if the difference of the adjacent elements isn't less than $D$, neither the difference of the first of these elements with an other element will be.
I wrote this algorithm:
Code:
Algorithm(D,E,K){
found=0;
for (i=1; i<=n; i++){
A[i]=D[i];
}
for (i=1; i<=m; i++){
A[n+i]=E[i];
}
HeapSort(A);
j=1;
p=2;
while (j<=n+m and p<=n+m and found==0){
if (abs(A[j]-A[p]) <= K) found=1;
j++;
p=j+1;
}
if (found==0) printf("NO\n");
else printf("YES\n");
}Could you tell me if my idea is right? (Thinking)
Last edited: