1. ## Comparing Arrays

I have a question which i totally have no idea on how to start, so i am hoping for some hint, say like give me an idea on how many times i should compare for each element in A if u know?

Given two arrays A and B containing n and m integers respectively, determine the set of integers that occur in A and B. You may assume that n>m>5. Your solution must satisfy the following conditions:
(1)Let X be an element in A. In order to identify whether X occurs in B, you required to compare X with one or more elements in B. However, you MUST NOT compare X with all the elements in B;

(2) You are not allowed to sort the elements in A or B

eg:
A= [2, 8, 6, 15, 23, 12, 7]
B= [15, 10, 6, 31, 3, 4, 7]

Then the set of identical integers will be [6,7]

2. >> you MUST NOT compare X with all the elements in B
>> You are not allowed to sort the elements in A or B

Either it's a trick question or you paraphrased your homework incorrectly....

Post the question exactly as it appears and your best attempt to solve it. If you have no idea at all - post some of the things you thought about and why those things don't work.

gg

3. There is no mistake in the question(it is as it is, except it was indicated that i am only required to write a pseudocode). I seriously have no idea on what should i do. This question would have been very easy if i can sort the array and do a binary search or compare with all the elements. They are the very reasons why i cant solve the question.

I contemplate that we might need some data structures such as tree(but then again that is some form of sorting). I cant think of any way to implement a queue or stack.

Maybe it might help if you know that this question from my course on data structures.

4. >> you MUST NOT compare X with all the elements in B

This is a clue to the solution.
There is currently no ordering on B, so it is impossible to identify whether X occurs in B without checking every element in B.

>> You are not allowed to sort the elements in A or B
...
>> we might need some data structures such as tree(but then again that is some form of sorting).

Well, I see "sortting the B array" and "inserting the elements of B into some ADT" as two different things (ie. not the same).

Of course, you can always ask your teacher/prof. what counts as "sorting the elements in A or B".
Also remember that solutions usually involve some recently studied ADT or algorithm.

Poorly worded question none the less....

gg

5. The assigment says:

Originally Posted by Raison
Given two arrays A and B containing n and m integers respectively, [...]
You may assume that n>m>5.
but then gives an example...

Originally Posted by Raison
A= [2, 8, 6, 15, 23, 12, 7]
B= [15, 10, 6, 31, 3, 4, 7]
... where n==m. Also note, 6 shares the same index in both A and B. Same goes for 7. 15 is also present but at different indices. This example is supposed to return:

Originally Posted by Raison
[6,7]
15 is not in there. The way I understand this assigment is that you are supposed to compare index n in A with index n in B. In this case X of A only needs to be compared with 1 element in B. Certainly this would be a bit easy, right?

6. The way I understand this assigment is that you are supposed to compare index n in A with index n in B
but n can be larger than m, so i dont think that's the way the question wants me to compare.

And btw i miss out one last statement:
Observe that in order to identify 7, you must not compare it with all the elements in B.

Sorry about that. But i wonder if that's gonna help.

7. What was the last couple of concepts studied in that class?

It's a poorly worded question that's probaly being over-analysed.....

>> Observe that in order to identify 7, you must not compare it with all the elements in B.
This is just more evidence that you can not simply use the un-ordered array B. The algorithm will involve some ADT/algorithm that will allow you to guarantee that an element is not in the ADT without comparing every element in the ADT.

gg

8. Originally Posted by Raison
but n can be larger than m, so i dont think that's the way the question wants me to compare.
Judging by the assignment you posted, it must be bigger than m. It isn't in the example, so either the example or the assignment is wrong. (heh.. or I)

Also what about the 15? Why isn't it returned in the example? It's in both arrays - another mistake or intention? If it is intended than you are not supposed to cross-compare the indices.

Anyway, I'm not trying to convince you here, just saying how I would understand it. Of course, this would render the assignment trivial, which doesn't really make sense either

9. Originally Posted by Raison
you required to compare X with one or more elements in B. However, you MUST NOT compare X with all the elements in B;

ur allowed to compare x with 1 or more elements in B yet u must not compare all the elements in B.

hmmm

or u can compare array length - 1. so now u r comparing all the elemnts in B except 1 with satisfies
you MUST NOT compare X with all the elements in B;

right?

10. It's a past year exam qn, so i dont think my most recent topic can give a clue.

Nyda:
I think u r right. There must be something wrong with the qn. Why isnt 15 part of the set?

I'm gonna just take it as a simple binary search qn. Sorry to waste ur time guys.

Really appreciate ur great help anyway!

11. The only way I can see that this would work would be if the two arrays were relatively sorted.
In the example given, the 7 was AFTER the 6 in both arrays. If that is true for any pair of numbers in common between the two arrays, then you can restrict the searches to the tail part of the array.

Example, having found 6 is common to both arrays, searches for 15, 23, 12, 7 would only need to search through 31, 3, 4, 7

Given that you state "You may assume that n>m>5.", you iterate through the smaller array, with the hope of skipping large gaps in the larger array.

> I'm gonna just take it as a simple binary search qn. Sorry to waste ur time guys.
This only works when the arrays are sorted, which you've eliminated as an option.