Consider the following scenario and then develop an algorithm to solve it: a) Su
ID: 3906313 • Letter: C
Question
Consider the following scenario and then develop an algorithm to solve it:
a) Suppose you have 9 coins and one of them is heavier than others. Other 8 coins weight equally. You are also given a balance. Develop and algorithm to determine the heavy coin using only two measurements using the balance.
b) Now, suppose you have n coins and one of them is heavier. You can assume that n is a power of 3. Generalize the algorithm you have developed in part (a) above for this case. What is the running time of your algorithm?
Explanation / Answer
a)
FindHeavyCoin(coins[9]):
1. Let array coins[] represents all the coins
2. Divide coins[] into three equal bundles each having three coins, index 0-2, 3-5, 6-8 say b1 b2 b3
3. Pick any two bundles at random and put them on the balance[say b1 and b2]
4. If b1 and b2 weigh same:
// b3 has heavier coin
Pick any two coins from 6-8 and put them on the balance [say 6 and 8]
If they weigh same:
third coin is the heavier coins [say 7]
else
The one which is heavier on the balance is the coin [either 6 or 8]
else
// the bundle which is heavier on the balance has the coin [say b1]
Pick any two coins from heavier bundle on the balance [say 0 and 1]
If they weigh same:
third coin is the heavier coins [say 2]
else
The one which is heavier on the balance is the coin [either 0 or 1]
b)
FindHeavyCoin(coins[]):
1. Let array coins[] represents all the coins
2. Divide coins[] into three bundles of equal sizes of size n/3
3. Pick any two bundles at random
4. while(sizeof(b1)>1 && sizeof(b2)>1)
If findHeavier(b1,b2):
// b3 has heavier coin
FindHeavyCoin(b3)
else
// If b1 is heavier
If b1 is heavier:
FindHeavyCoin(b1)
else
FindHeavyCoin(b2)
findHeavier(bun1, bun2):
If bun1 and bun2 weigh equal:
return true
else
return false
Time complexity: O(log3n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.