1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Bumek [7]
3 years ago
13

Suppose you are consulting for a bank that's concerned about fraud detection, and they come to you with the following problem. T

hey 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 is 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 question with only O(n log n) invocations of the equivalence tester.
Computers and Technology
1 answer:
iren [92.7K]3 years ago
8 0

Answer:

Explanation:

( 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 at most n

You might be interested in
3.2 lesson practice edhesive ​
Nookie1986 [14]
Ummm what is the question
6 0
3 years ago
You would set a ___________ to prevent users from immediately changing their password several times in one day to return to the
Temka [501]

Answer:

The answer is (B) Maximum password age.

Explanation:

To prevent several changing of passwords by a user in a day, the maximum times a password can be rest within a day is normally set by  the system administrator.

The setting ensures the password is returned to the current settings of the password on the system for the user and prevents unnecessary changing of passwords in a day by user.

6 0
3 years ago
Read 2 more answers
How to print<br> 1<br> 321<br> 54321<br> 7654321<br> triangle pattern in python
krok68 [10]

Hope this helps, Upvote if you like it :)

6 0
2 years ago
6.Decreasing a telescope's eyepiece focal length will:
Ghella [55]
B is the correct answer to ur questions
8 0
3 years ago
A ________ pays out cash flows from a collection of assets in different tranches, with the highest-rated tranch paying out first
KonstantinChe [14]

Answer:

The correct option to the following question is CDO(Collateralized Debt Obligation).

Explanation:

CDO(collateralized debt obligations), is the financial tool that is used by the banks to repackage the individual loans into the product sold to the investors on secondary markets.

It developed as the instruments for corporate debts markets, after the year 2002, CDO became the vehicles for refinancing the mortgage backed the securities.

A CDO is the type of the structured asset backed security.

3 0
3 years ago
Other questions:
  • Holly Carpenter argues that technology may actually prevent some kinds of evolution that would benefit humans. Do you agree with
    8·2 answers
  • _____________ refers to know-what and know-why of technology.
    12·1 answer
  • Technically
    12·1 answer
  • Which type of computer operating system would be best for a large corporation?
    7·2 answers
  • Networking and telecommunications technologies, along with computer hardware, software, data management technology, and the peop
    5·1 answer
  • Please help! 40 points + Brainliest!
    8·1 answer
  • You are troubleshooting a client connectivity problem on an Ethernet network. The client system has intermittent connectivity to
    9·1 answer
  • Pls help will give brainlest!!! The image shows a line graph. Which scientist is most likely to use this visual aid in a present
    15·1 answer
  • What is a benefit of an account with interest?
    5·1 answer
  • At a family reunion, your cousin takes a picture of both of you with her phone, orders a print of it, and mails it to you with a
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!