Algorithms. A coin collector has a large collection of antique gold doubloons (a

Question

Algorithms. A coin collector has a large collection of antique gold doubloons (an old Spanish currency), but she suspects that one of these coins is a fake. The only way to detect the forgery is by its weight, which may be lighter or heavier than a genuine doubloon. She has an old-fashioned scale that is large enough to hold all of her coins, and will indicate if one pile of coins is lighter, heavier or the same weight as another pile of coins.

a) (Pseudocode) Assuming the fake coin is lighter than a genuine coin, write a divide-and-conquer algorithm that determines which coin is fake by repeatedly diving the n coins into two equal-sized piles (with one coin left over if the number of coins is odd).

b) Write a recurrence equation for the worst-case number of weighings required for this algorithm.

c) Assuming the fake coin may be lighter or heavier than the genuine coin, build a decision tree for a solution to the instance of the problem where there are three coins, and each decision corresponds to a single weighing.

d) Prove that the worst-case number of weighings for this version of the problem is (left ceiling) log3(2n+1) (right ceiling).

e) Write an algorithm that solves this version of the problem whose worst case is closer to the lower bound above (Hint: divide the coins into three piles instead of two.)

If someone would be able to help walk me through this example problem it would be greatly appreciated! Thank you!

Explanation / Answer

Solution:

a)

The above algorithm is dividing the coins into three halves and which ever is lighter will be kept on dividing and weighting until the base case detects which one is the fake coin is.

b)

The recurrence relation for the above algorithm is

T(n)= T(n/3)+n, considering n number of coins are there.

After solving the above recurrence using master theorem we can conclude that the time complexity of the above algorithm will be O(log n).

d)

In worst case the coin will be found at the last iteration of the recurrence, and the steps in worst case to find out the fake coin will be (ceil) (log3n).

I hope this helps. Don't forget to give a thumbs up if you like this.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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