You have n coins of the same kind, one of which is bad it is slightly heavier than the others. You

want to find out the bad coin, and the only thing you have is a scale on which you can weigh any set

of coins against another set of coins.

(a) Design an algorithm to find out which one is bad, your algorithm should minimize the number of

weighs required until the bad one is found.

Problem 5. (20 pts) You have n coins of the same kind, one of which is "bad" t is slightly heavier than the others. You want to find out the bad coin, and the only thing you have is a scale on which you can weigh any set of coins against another set of coins. (a) Design an algorithm to find out which one is bad, your algorithm should minimize the number of weighs required until the bad one is found. (b) Prove your algorithm is optimal. That is, if the algorithm that you design makes in the worst-case w weighs, then show that any other algorithm that is guaranteed to find the bad coin must also make w or more weighs in the worst-case. (c) Consider the case that the bad 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 weighs you will need to find the bad coin among 12 coins? Describe your algorithm