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
When should you use a union type component in a structured variable?
Eduardwww [97]

Answer:

The answers to 1st question and part 2A is given. However, the 2B is not given complete and thus cannot be answered.

Explanation:

UNION is a keyword used in C Language to have a commonly shared memory that can be used by multiple elements. It is a data-type that allows different data types to use the same shared memory location.

Importance: If you want to minimize the use of memory by sharing it between different datatype variables, then use UNION. For Ex. Let's suppose I want to use 2 variables a and b of type char and int respectively. Now, suppose int takes memory space of 2 bytes and char takes 1 byte then the total amount of memory needed = 2 + 1 = 3 Bytes. But, we want to first make use of a, and once done, we want to declare variable b. We can limit the memory use by declaring a memory space of 2 bytes (max of a and b). First, we can use this space to store the int variable and when done with it, we can use it to store the char variable.

PART 2A

typedef struct{

  int partNum;

  char partName[25];

} partin;

#define Partin partin

7 0
3 years ago
How do you set up nordvpn with spectrum?
Setler [38]

Answer:

simple

Explanation:

use nordvpn with discount code: Chonchode

7 0
3 years ago
Which of the following emergencies are weather-related? A. Ice storm B. Hurricane C. Earthquake D. A and B
Angelina_Jolie [31]

Answer:

The answer is D. A and B

Explanation:

I think the answer is D because Ice storms are caused by freezing rain and Hurricanes are formed near the equator over warm ocean waters. both of them are weather-related.

5 0
3 years ago
Read 2 more answers
Who watched Unus Annus??? (If you did what was your favorite part?​
quester [9]

This video was completeley unedited was a banger, and so was the vid where they made robot amy. that was hilarious.

But since it is now Post Mortem all say here is...

Unas Annus. Memento Mori.

It sure was fun.

3 0
3 years ago
What will be displayed after the following statements execute? int funny = 7, serious = 15; funny = serious % 2; if (funny != 1)
Reika [66]

Answer:

1 1

Explanation:

First we have funny = 7 and serious = 15 .Then after that remainder when serious is divided by 2 is stored in funny that is 1.if condition will be false because funny is equal to 1.else if condition will also be false because it is not 2.So else will be executed and funny =1 and serious =1.

Output=1 1

8 0
4 years ago
Read 2 more answers
Other questions:
  • For a project called "The Sheep Market", Aaron Koblin collected drawings of sheep from strangers on the Internet. He posted the
    14·1 answer
  • A(n) file management system is a program that allows the creation of individual database tables, each of which is stored in its
    5·1 answer
  • Data_____is defined as the condition in which all of the data in the database are consistent with the real-world events and cond
    9·1 answer
  • Given an int variable k, an int array incompletes that has been declared and initialized, an int variable studentID that has bee
    10·1 answer
  • Hard light is usually not good for filming. True False
    11·2 answers
  • I WILL GIVE BRAINLIEST TO WHO ANSWERS FIRST AND CORRECTLY.
    6·2 answers
  • What constructs break or bend the normal Syntax patterns of scheme?
    15·1 answer
  • Which option identifies what the computer will yield in the following scenario?
    10·1 answer
  • Create a list called courses containing the names of your current courses.
    9·1 answer
  • Computer are most wonderful creation of 21st century how ?​
    15·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!