Problem 5. (20 marks) You have n coins of the same weight, except for \"special\
ID: 3727819 • Letter: P
Question
Problem 5. (20 marks) You have n coins of the same weight, except for "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 nd 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
Solution:
a)
The brute force algorithm is given below:
Algorithm:
In the worst case, the last coin will be the one which was fallen, so the number of times we used the scale will be
= n-1
In divide and conquer approach we will follow the following steps:
The above algorithm will take log n comparisons to find the coin.
b)
As far as optimality of the algorithm is concerned it is for sure that divide and partition
have to happen because any other algorithm will take the number of weighings. Currently,
we are partitioning 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 constant
quantity.
c)
The number of weighings as per the algorithm 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.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)