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
Among object-oriented languages, one feature that varies considerably is whether the language allows multiple inheritance. C++ d
Amiraneli [1.4K]

Multiple inheritance causes Diamond problem which happens when:

Class A is parent of class B and C

Now when class D will be inherited from both Class B and C it will have all the members of class A and B which if same will confuse the compiler to import which one?

C++ solves it by using virtual keyword with them and thus telling the compiler which one to inherit.

Java has introduced the interface concept rather then allowing multiple inheritance.

4 0
3 years ago
An open system consists of nonproprietary hardware and software based on publicly known standards that allows third parties to c
kolezko [41]

Answer:

The answer is "Option D".

Explanation:

A system or a group of components that communicate with your environment through the sharing of resources, materials, and knowledge with a view to system regeneration and development is known as an Open system. In other words, we can say that it is a system that includes a non-proprietary hardware and advert-based software which enables third parties to add or interact with products to plug in the system and It is freely available on the internet. In this question, the incorrect options can be described as follows:

  • In option A, The management system is used by an organization. It is a paid system that's why it is not correct.
  • In option B, This system enables users in online communities and evaluates one another that's why it is not correct.
  • In option C, This type of system provides resources for upgrade user knowledge. It is a paid system that's why it is not correct.  

6 0
3 years ago
What is spread sheet software?​
melamori03 [73]

Answer:

The answer to this question is given in the explanation section.

Explanation:

This is a type of software which show us data in tabular form. These software can easily store, analyze and organize data.

They are divided in rows and columns. They are mainly used for accounting and book keeping.

The commonly used spread sheet software in the market are MS Excel by Microsoft, Calc by libre office.

3 0
3 years ago
Match the data type to the given data.
guapka [62]
Float: 26.2
Array: c, o, m, p, u, t, er
Boolean: false
Character: c
7 0
3 years ago
Read the poem again and work in pairs or groups to do the following tasks.
kap26 [50]

Answer:

i have no idea what the answer is

Explanation:

8 0
3 years ago
Other questions:
  • Jordan has been asked to help his company find a way to allow all the workers to log on to computers securely but without using
    6·1 answer
  • Assume that name and age have been declared suitably for storing names (like "abdullah", "alexandra" and "zoe") and ages respect
    14·1 answer
  • What part of a check is the LEAST important?
    14·2 answers
  • How would you describe the relationship between blocks of code and commands?<br>HELP​
    10·1 answer
  • Jonathan works with a team of graphic designers. They have a collection of images and have divided the image editing work among
    5·2 answers
  • 4. What are the ethical issues of using password cracker and recovery tools? Are there any limitations, policies, or regulations
    5·1 answer
  • To quit, a user types 'q'. To continue, a user types any other key. Which expression evaluates to true if a user should continue
    7·1 answer
  • What are the steps to customize a slide show?
    10·2 answers
  • A slide titled Alexander Graham Bell. There are 6 bulleted entries on the slide, and there is a lot of text on the slide. There
    11·2 answers
  • Which of the following are drivers of machine learning growth?
    15·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!