It is possible to do that with only O(n) invications, i answered it already to this group...
2009/4/1 DragonZsnakE <dragonzsn...@gmail.com> > ( n cards are there initially ) > > we pick out the first card in random it takes n-1 comparisons to figure out > its Equivalence card - n-1 steps > Two cards have been eliminated ( this leaves us with 2 and n-2 cards) > we pick out the 2nd card in random it takes n-3 comparisons to figure out > its Equivalence card - n-3 steps > we continue to do this.. till all cards are exhausted ( leaves us with 2 > and n-4 cards again) > the last comparison will > have > - n-(n-3) > > the sum of all these steps - (n-1) + (n-3) + (n-5) + .........+ > (n-(n-3)) > > if you draw this in the form of a tree. > > > n - n > 2 > n-2 - n > 2 > n-4 - n-2 > 2 > n-6 - n-4 > 2 > n-8 - n- 6 > > > the height of the tree will be log n , sum @ each level is atmost n > > so Big oh(n log n) > > > > > > > > On Wed, Apr 1, 2009 at 10:53 AM, hanumant <hanuman...@gmail.com> wrote: > >> >> Suppose you are consulting for a bank that’s concerned about fraud >> detection, and they come to you with the following problem. They have >> a collection of n >> bank cards that they’ve confiscated, suspecting them of being used in >> fraud. Each bank >> card is a small plastic object, containing a magnetic stripe with some >> encrypted data, and >> it corresponds to a unique account in the bank. Each account can have >> many bank cards >> corresponding to it, and we’ll say that two bank cards are equivalent >> if they correspond to >> the same account. >> It’s very difficult to read the account number off a bank card >> directly, but the bank has a >> high-tech “equivalence tester” that takes two bank cards and, after >> performing some >> computations, determines whether they are equivalent. >> Their question is the following: among the collection of n cards, is >> there a set of more >> than n/2 of them that are all equivalent to one another? Assume that >> the only feasible >> operations you can do with the cards are to pick two of them and plug >> them in to the >> equivalence tester. Show how to decide the answer to their questions >> with only O(n log n) >> invocations of the equivalence tester. >> >> >> Also can someone point me to where i can get additional problems? >> >> Thanks >> >> >> >> --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
