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.

Solutions

Expert Solution

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

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.

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...

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...

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

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...

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? 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 HAD POSSIBLE SCORES RANGING...

Research the hexagonal numbers whose explicit formula is given by Hn=n(2n-1) Use colored chips or colored...

Research the hexagonal numbers whose explicit formula is given by Hn=n(2n-1) Use colored chips or colored tiles to visually prove the following for .(n=5) [a] The nth hexagonal number is equal to the nth square number plus twice the (n-1) ^th triangular number. Also provide an algebraic proof of this theorem for full credit . [b] The nth hexagonal number is equal to the (2n-1)^th triangular number. Also provide an algebraic proof of this theorem for full credit. please use...

Subjects