5. A bank has issued two separate sets of account access cards, set A and set B.

Question

5. A bank has issued two separate sets of account access cards, set A and set B. Each set consists of n cards and for every card in the set A there is a corresponding card in the set B that belong to the same account, and we will refer to these two cards as the matching pair. Each card is a small plastic object containing a magnetic strip with some encrypted number that corresponds to a unique account in the bank. It is required to find all matching pairs. There is a card reader machine such that when two cards, one from set A and one from set B, are inserted in the machine one of its three light indicators turns on; green if the pair matches, red if the account number on A is larger than B, and yellow if the number on B is higher than that of A. However, the card reader cannot compare two cards belonging to the same set. (a) Describe an algorithm in clearly defined step that uses Theta(n^2) tests to find the matching pairs. (b) Describe a more efficient algorithm with an average case complexity of. O(n lg n) tests to find the matching pairs. Prove that your algorithm satisfies the desired complexity.

Explanation / Answer

matching in O(n2)

we will pick a card from set A and one by one match it with card from set B until we will find it match in set B.

pseudo code =>

function matching(Set A,Set B):
   for a in Set A:
       for b in Set B:
           if (match(a,b) == true):   # can check this from machine                  
               match found for element a in Set A

time complexity for algorithm

for finding a match for a element in Set A we need to check its match in Set B until we will not find it.
so for finding a match for a element in Set A we need O(n) running time.

for finding match for all element in Set A clearly we need O(n2) running time.

efficient algorithm for finding matching:

You can use card form A set as pivot for quick selection of set B. So you can implement quicksort in this way. So select one card from set A and divide B set to smaller and bigger. If you found matching card in B you can use this card to divide A set. If you not found matching card repeat. If found apply algorithm to smaller and bigger groups in same way as in quicksort. Repeat until you find all matching cards. Complexity is same as for quicksort, so O(N logN) in average.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.