Thread: Comparing Arrays

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    133

    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. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    >> 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. #3
    Registered User
    Join Date
    Sep 2003
    Posts
    133
    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. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    >> 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. #5
    Registered User
    Join Date
    Apr 2004
    Posts
    210
    The assigment says:

    Quote 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...

    Quote 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:

    Quote 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?
    Last edited by Nyda; 04-20-2004 at 07:38 AM.

  6. #6
    Registered User
    Join Date
    Sep 2003
    Posts
    133
    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. #7
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    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. #8
    Registered User
    Join Date
    Apr 2004
    Posts
    210
    Quote 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. #9
    Registered User
    Join Date
    Mar 2004
    Posts
    494
    Quote 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;
    isnt the above a contradiction?

    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. #10
    Registered User
    Join Date
    Sep 2003
    Posts
    133
    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. #11
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Comparing Arrays question
    By taugust7 in forum C++ Programming
    Replies: 36
    Last Post: 04-14-2009, 12:29 PM
  2. Comparing elements of character pointer arrays
    By axe in forum C Programming
    Replies: 2
    Last Post: 11-14-2007, 12:20 AM
  3. Comparing 2 elements from 2 different arrays
    By Dan17 in forum C Programming
    Replies: 3
    Last Post: 11-15-2006, 02:43 PM
  4. comparing arrays
    By dustyrain84 in forum C Programming
    Replies: 1
    Last Post: 01-21-2004, 05:52 PM
  5. Comparing Character Arrays
    By LostNotFound in forum C++ Programming
    Replies: 2
    Last Post: 02-23-2003, 12:42 PM