Problem 5. (20 marks) You have n coins of the same weight, except for a \"specia

Question

Problem 5. (20 marks) You have n coins of the same weight, except for a "special" one which is slightly heavier. You want to find out this special coin. The only thing you have is a scale on which you can weigh any set of coins against another set of coins. a. (7 marks) Design an algorithm to find out which one is the special coin, your algorithm should minimize the number of weighings required until the special coin is found. b. (7 marks) Prove your algorithm is optimal. That is, if the algorithm that you design makes in the worst-case w weighings, then show that any other algorithm that is guaranteed to find the special coin must also make w or more weighings in the worst-case c. (6 marks) Consider the case that the special coin could either be heavier or lighter than the others. That is, you know its weight is different from the others, but whether it is heavier or lighter is unknown In the worst-case, what is the minimum number of weighings you will need to find the special coin among 12 coins? Describe your algorithm

Explanation / Answer

The alogorithm is as follows:

The special coin is heavy:

We will divide the coins into two parts. The part which is heavy will have the special coin.
Again we will repeat the whole process. We will keep on doing till we get a pair of coins and
we will br through.

The complexity of the aogorithm will be log(n) as it is equivalent to the depth of a binary
tree.

As far as optimality of the algorithm is concernes it is for sure that divide and partition
has to happen because any other alogorithm will take more number of weighings. Curretly
we are partioning equally , other options can be of varying sizes.But in such situations if
it happens to be in smaller partition, the number of weighings will be less but again thats a
matter of probabiilty. If it is in a biggeer partition we will be needing more number of
weighings. So dividing equally gives us optimal number of weighings in the worst case.

Now considering we don't know whether it is haevy or light in that case, we will be needing
one extra weighing to determine which half is having the special one. For example at the
first level with n/2 partition, we determined which part is having the spacial one by weighing
both the parts (when we knew it is heavy), so we persued our serach with the heavier half but
now if we don't now whether it is heavy or light so we need one more partition for both the
halves. The partition not having the special one will get divided into two halves with equal weights and the partition which is having the special one will get divided into unequal halves
in terms of weight. So the complexity won't change much and it will be increased by a contant
quantity.

Coming to 12 coins

The number of weighings as per the alogorith is as follows:

1. Weight 6 - 6 coins
2. Weight 3 - 3 coins
3 Weight 2 coins,   1 is left
4. if 2 are of same weight, the one left is the special one
5. If 2 are of different weight, the heavier one is the special one

So total 4 weighings.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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