This lab can be done in teams of 1 or 2
Fake Coin Problem
The Fake Coin Problem is explained on pages 152-153 of your textbook.
Here is a summary:
||You have a pile of n identical looking coins including one fake which is
lighter than all the others.
You also have an old-fashioned
You can design an efficient algorithm which uses the scale to find the fake coin:
Hopefully you have recognized that since the problem is cut in half at each iteration,
this is yet another wonderful algorithm of order log2n.
- Divide your coins into 2 identically sized piles.
If you had an odd number of coins then there will be an extra coin that you will put aside
- Put one pile of coins on one of the balance's platters and the other pile on the other platter.
Here are the possible outcomes:
- If one platter is lighter than the other, you will know that the fake coin is in the
lighter platter. In this case, you can repeat the algorithm with the coins from that platter
only and discard all the other coins including the extra you had put aside if n was odd.
Of course, if there was only one coin on each platter,
then the fake coin is the lighter of the two.
- If n is odd it is also possible that the fake coin is the one that was put aside
when the original pile was split into 2.
You will know that this is the case because all the other coins will weight the same and
therefore the two piles of coins in the balance's platters will weight the same.
In that case you have also found the fake coin.
In this lab, you will now get to improve this great algorithm!
Formalization of the Fake Coin solution
Before we get to your lab, let's get a bit more formal:
Pseudocode for Findfake2
The algorithm above can be described in pseudocode as follows:
// Findfake2(coinpile, n) returns Coin
// Coin is a data structure representing coins
// coinpile is a Collection of Coins
// n is the size of coinpile
// It is known that there is one fake coin in coinpile
if n=1 return the first coin in coinpile
halfn = n div 2
pile1 = Collection of coins consisting of the first halfn elements of coinpile
pile2 = Collection of coins consisting of the next halfn elements of coinpile
compareweight = Weigh(pile1,pile2)
if compareweight = -1 return Findfake2(pile1, halfn)
if compareweight = 1 return Findfake2(pile2, halfn)
return nth coin in coinpile
// Weigh (coinpile1, coinpile2) returns:
// -1 is coinpile1 weighs less than coinpile2
// 0 if coinpile1 and coinpile2 weigh the same
// 1 is coinpile1 weighs more than coinpile2
Analysis of Efficiency of Findfake2
- The size of the problem is n = # of coins in coinpile
- The basic operation is a function call to the Weigh function.
- The best case scenario is when n is odd and the fake coin is the last coin
of the coinpile collection. In that case Weigh will only be called once
and therefore Findfake2 is O(1) in the best case.
- The worst case scenario is when the decision is only made when weighing two
coins against each other after all the other coins have been discarded
(except possibly for a third one if n=3 in the last function call).
In this case, since Findfake2 is recursive,
we need to set up a recurrence relation for its cost, as follows:
Let C(n) = #of times the function Weigh is called when coinpile had n elements
C(1)=0; C(n)=1+C(floor(n/2)) if n>1
This recurrence relation is more or less the same as the one
we saw in the algorithm to find the binary representation of an integer, and also in the
binary search algorithm. The difference is in the starting condition.
As in these two algorithms, the recurrence relation is solved by first assuming that
floor(n/2)=n/2 at each step. In other words that n=2k from some k.
This changes the recurrence relation to
C(20)=0; C(2k)=1+C(2k-1) if k>0
Substituting back into the recurrence relation, you get
C(n) = C(2k)=1+C(2k-1) = 1+1+C(2k-2) = 1+1+1+C(2k-3) =
... = k+C(2k-k) = k + C(20) = k+0 = k = log2n
This lab is inspired by exercise 4.4.10 of the textbook.
You will be asked to improve the Findfake2 algorithm by splitting each pile of coins
into more than 2 piles at each step.
For the entire lab, you will assume that the basic operation is a function call to the Weigh
function and you cannot change this function.
This lab should be done directly in the solution sheet
- See the Lecture Material for
the Mathematical Analysis of Algorithms and for Decrease and Conquer
- Textbook chapters 2.4 and 4.4
This lab is a
paper submission to be handed in at the Computer Science office.
- Hand in a printout of your solution/marking sheet
- In addition to the lab itself you will need to also submit the Lab Submission Declaration on D2L. This lab will not be graded unless this declaration has been submitted