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]
2 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]2 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 you see ##### in a cell, you should A. increase the cell width. B. increase the cell height. C. decrease the cell width. D.
Usimov [2.4K]
A. Increase the cell width this is because there is not enough room in the cell to display the number that was given. 
4 0
3 years ago
Develop a C program that calculates the final score and the average score for a student from his/her (1)class participation, (2)
Ghella [55]

Answer:

#include <iomanip>

#include<iostream>

using namespace std;

int main(){

char name[100];

float classp, test, assgn, exam, prctscore,ave;

cout<<"Student Name: ";

cin.getline(name,100);

cout<<"Class Participation: "; cin>>classp;

while(classp <0 || classp > 100){  cout<<"Class Participation: "; cin>>classp; }

cout<<"Test: "; cin>>test;

while(test <0 || test > 100){  cout<<"Test: "; cin>>test; }

cout<<"Assignment: "; cin>>assgn;

while(assgn <0 || assgn > 100){  cout<<"Assignment: "; cin>>assgn; }

cout<<"Examination: "; cin>>exam;

while(exam <0 || exam > 100){  cout<<"Examination: "; cin>>exam; }

cout<<"Practice Score: "; cin>>prctscore;

while(prctscore <0 || prctscore > 100){  cout<<"Practice Score: "; cin>>prctscore; }

ave = (int)(classp + test + assgn + exam + prctscore)/5;

cout <<setprecision(1)<<fixed<<"The average score is "<<ave;  

return 0;}

Explanation:

The required parameters such as cin, cout, etc. implies that the program is to be written in C++ (not C).

So, I answered the program using C++.

Line by line explanation is as follows;

This declares name as character of maximum size of 100 characters

char name[100];

This declares the grading items as float

float classp, test, assgn, exam, prctscore,ave;

This prompts the user for student name

cout<<"Student Name: ";

This gets the student name using getline

cin.getline(name,100);

This prompts the user for class participation. The corresponding while loop ensures that the score s between 0 and 100 (inclusive)

<em> cout<<"Class Participation: "; cin>>classp; </em>

<em> while(classp <0 || classp > 100){  cout<<"Class Participation: "; cin>>classp; } </em>

This prompts the user for test. The corresponding while loop ensures that the score s between 0 and 100 (inclusive)

<em> cout<<"Test: "; cin>>test; </em>

<em> while(test <0 || test > 100){  cout<<"Test: "; cin>>test; } </em>

This prompts the user for assignment. The corresponding while loop ensures that the score s between 0 and 100 (inclusive)

<em> cout<<"Assignment: "; cin>>assgn; </em>

<em> while(assgn <0 || assgn > 100){  cout<<"Assignment: "; cin>>assgn; } </em>

This prompts the user for examination. The corresponding while loop ensures that the score s between 0 and 100 (inclusive)

<em> cout<<"Examination: "; cin>>exam; </em>

<em> while(exam <0 || exam > 100){  cout<<"Examination: "; cin>>exam; } </em>

This prompts the user for practice score. The corresponding while loop ensures that the score s between 0 and 100 (inclusive)

<em> cout<<"Practice Score: "; cin>>prctscore; </em>

<em> while(prctscore <0 || prctscore > 100){  cout<<"Practice Score: "; cin>>prctscore; } </em>

This calculates the average of the grading items

ave = (int)(classp + test + assgn + exam + prctscore)/5;

This prints the calculated average

cout <<setprecision(1)<<fixed<<"The average score is "<<ave;  

8 0
3 years ago
Copy the 10 statements as they appear below into your journal.
AURORKA [14]

B A C D C A B B CDAAD

4 0
3 years ago
Read 2 more answers
Windows uses a memory-management technique known as ________ to monitor which applications you use most frequently and then prel
lukranit [14]

Answer:

SuperFetch

Explanation:

Superfetch is a memory management technique on windows service that enables or fetch frequently use applications on systems and launch them faster because the frequently use applications has been preload into the system memory for easy access when they want to be used.

SuperFetch always takes notice of all application running on your system in which when you exit a frequently used application SuperFetch will preload them immediately since it is saved on the system memory.

One of the most important part of Superfetch is that it saves alot of time because you don't have to search the applications before you get access to them in as far as the application was frequently used.

5 0
2 years ago
True or false? malware problems and other compromises of your computer information are rare.
Marina86 [1]
I think that is false I am not 100% sure.
3 0
2 years ago
Other questions:
  • The git _____ command will display the last commit and what were the changes you made.
    9·1 answer
  • Create a program that reads words.txt (link near top of our home page) in order to: determine the length of the longest word(s)
    14·1 answer
  • Count input length without spaces, periods, or commas Given a line of text as input, output the number of characters excluding s
    8·2 answers
  • ____ is the official web portal for the U.S. government, providing access to all official U.S. government services and informati
    12·1 answer
  • A(n) ____________________ is hardware or software that blocks or allows transmission of information packets based on criteria su
    13·1 answer
  • Do you think that distributed OSs use a process-communication technique different from that used by desktop OSs?
    13·1 answer
  • A file name extension provides what information about a file?
    6·1 answer
  • Which of the examples is part of client-side code?
    12·1 answer
  • Reply emailing a student who is asking about audio materials​
    6·2 answers
  • 1 point
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!