we are given n chips which may be working or defective. A working chip behaves as...

we are given n chips which may be working or defective. A working chip behaves as follows: if we connect it to another chip, the original chip will correctly output whether the new connected chip is working or is defective. However, if we connect a defective chip to another chip, it may output any arbitrary answer (defective---->might say the other one is working /defective).

In the class, we saw that if strictly more than half the chips are working, then there is an algorithm that finds a working chip using O(n) tests.

1) Prove that even when we only have a single working chip and a single defective chip (i.e.,n = 2), there is no algorithm that can find the working chip in general.

Expert Solution

Colby Messinger answered 2 years ago

n chips manufactured, two of which are defective. k chips randomly selected from n for testing....

n chips manufactured, two of which are defective. k chips randomly selected from n for testing. Q1. What is Pr(a defective chip is in k selected chips) ? n persons at a party throw hats in a pile, select at random. Q2. What is Pr(no one gets own hat) ? Q3. Plot Pr (no one gets own hat) in the Y-axis and n=[1,1000] in the X-axis (~pmf)

Our event of interest is whether a defective chip is found in a set of chips,...

Our event of interest is whether a defective chip is found in a set of chips, and let Y be the number of chips that must be sampled until a defective one is found. The researchers estimate the probability of a defective chip at 30%. What is the probability that the 8th selected chip be the first defective one?

A potato chip company claims that their chips have 130 calories per serving. We think this...

A potato chip company claims that their chips have 130 calories per serving. We think this claim is too low, so we buy 40 bags of chips and test the calories per stated serving size. Our sample yields a mean of 132 calories per serving, with a standard deviation of 6 calories. Is the manufacturer's claim too low? \ Use alpha = 0.05.

A communication system consists of n antennas of which m are defective and n − m...

A communication system consists of n antennas of which m are defective and n − m are functional. Suppose the n antennas are indistinguishable and are lined up in a linear array. The system is called functional as long as no two consecutive antennas are defective. Suppose we randomly line up the n antennas. What is the probability that the resulting system will be functional?

n 1998, the Nabisco Company launched a “1000 Chips Challenge” advertising campaign in which it was...

n 1998, the Nabisco Company launched a “1000 Chips Challenge” advertising campaign in which it was claimed that every 18-ounce bag of their Chips Ahoy cookies contains 1000 chips (on average). A curious statistics student purchased 8 randomly selected bags of cookies and counted the chocolate chips. The data is given below: 1200 1019 1214 1087 1214 900 1200 825 a) The student concluded that the data was not normally distributed and wanted to use a Wilcoxon Signed-Rank test to...

Given an array A[1..n], with distinct values and k with 1 ≤ k ≤ n. We...

Given an array A[1..n], with distinct values and k with 1 ≤ k ≤ n. We want to return the k smallest element of A[1.....n], in non-decreasing order. For example: A = [5, 4, 6, 2, 10] and k = 4, the algorithm returns [2, 4, 5, 6]. There are at least the following four approaches: a. heapify A and then extract k elements one by one b. sort the array (e.g. using MergeSort or HeapSort) and then read the...

If a consumer is injured by a defective product, which of the following types of claims may the consumer bring? (Select two)

If a consumer is injured by a defective product, which of the following types of claims may the consumer bring? (Select two) Strict Liability Malfeasance Misdemeanor Negligence

7) A shipment of 10 items contains 4 items which are defective. If we randomly select...

7) A shipment of 10 items contains 4 items which are defective. If we randomly select 4 of the items for inspection, what is the probability of at least 3 non-defective items in the sample? Assume sampling without replacement. a) 185/210 b) 184/210 c) 25/210 d) 115/210* e) 175/210

The N-QUEENS PROBLEM Given a chess board having N x N cells, we need to place...

The N-QUEENS PROBLEM Given a chess board having N x N cells, we need to place N queens in such a way that no queen is attacked by any other queen. A queen can only attack horizontally, vertically and diagonally. Let’s go at this one step at a time. let’s place the first Queen at some cell, (I, j) and now the number of unattackable cells are reduced. And now, the number of the Queens to be placed are N...

1.(0.5) IF WE ARE GIVEN THE POPULATION STANDARD DEVIATION AND n > 30 DO WE USE...

1.(0.5) IF WE ARE GIVEN THE POPULATION STANDARD DEVIATION AND n > 30 DO WE USE THE z-VALUES OR t-VALUES? We would use Z values NOW SHOW WHAT YOU HAVE LEARNED SO FAR WITH DESCRIPTIVE AND INFERENTIAL STATISTICS.YOU ARE PROMOTING ONE I.T. EMPLOYEE AND HAVE TWO CANDIDATES THAT HAVE EACH TAKEN THE SAME 15 SECURITY EXAMS OVER THE PAST YEAR. YOU HAVE TWO FINALIST CANDIDATES WHO HAVE THE FOLLOWING SCORES. SO, WHICH ONE DO YOU PICK AND WHY? (EACH TEST...

Question