You are given n = 2k coins, all of which look identical. However, one of the coi

Question

You are given n = 2k coins, all of which look identical. However, one of the coins is defective – it weighs either slightly more or slightly less than the rest (you don’t know which). You also have at your disposal an electronic equivalence tester, which has two compartments. You may place any set of objects in each compartment; the tester tells you whether or not the two sets weigh the same. Note that the tester does not tell you which side is heavier and which one lighter – only whether they weigh the same or not. Your goal is to determine which of the coins is defective using the tester at most k times. You may assume that k > 1, that is, n > 2. (Is it possible to find the defective coin when n = 2?) Note that you are allowed to use the tester only k times, not O(k) or k plus a few more times. You will receive partial credit for slightly worse solutions.

(a) Describe a divide and conquer algorithm for this problem.

(b) Argue that your algorithm uses the tester at most k times.

(c) Prove the correctness of your algorithm, in other words that it always correctly identifies the defective coin.

Explanation / Answer

As per your requirement the below one is solution please follow it

A)

Divide and quanqer will help to devide the problem into two halves each time, thus the total number of camparisons are reduced by half at each stage. For example if no of coins = 2000, sorting could be optimized by deviding the coins intothree part.

B)

But in this case the value of comparisons must be greaterbecause of devision operators of 2000 for 3. so estes must be greater than 7 in this case. If this is the case then again we will bring the total number of comparisons from 3 to 2 to make sure that comparison will not exceed value of K, which would be 10 in that case.

C)

Comparison will lead to two conclusions Heavy or light , consider heavier part all the time to filter the lighter part always or vice versa to identify defective coin in k or(k/2)+constant comparisons.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.