## CPS616 |
## W2017 Lab 5 | |

## Worth: 5% |
## Fake Coin Problem |
## Due: Monday March 20 |

## Team SizeThis lab can be done in teams of 1 or 2## Fake Coin ProblemThe Fake Coin Problem is explained on pages 152-153 of your textbook. Here is a summary:
You can design an efficient algorithm which uses the scale to find the fake coin: - 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 temporarily.
- 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.
- 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.
_{2}n.
In this lab, you will now get to improve this great algorithm! ## Formalization of the Fake Coin solutionBefore we get to your lab, let's get a bit more formal:## Pseudocode for Findfake2The 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 Findfake2(coinpile, n) 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>1This 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=2^{k}from some k. i.e. k=log_{2}n. This changes the recurrence relation to C(2^{0})=0; C(2^{k})=1+C(2^{k-1}) if k>0 Substituting back into the recurrence relation, you get C(n) = C(2^{k})=1+C(2^{k-1}) = 1+1+C(2^{k-2}) = 1+1+1+C(2^{k-3}) = ... = k+C(2^{k-k}) = k + C(2^{0}) = k+0 = k = log_{2}n
## Lab DescriptionThis 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 This lab should be done directly in the solution sheet (docx or pdf). ## Additional Material- See the Lecture Material for the Mathematical Analysis of Algorithms and for Decrease and Conquer
- Textbook chapters 2.4 and 4.4
## Hand InThis lab is a paper submission to be handed in at the Computer Science office. |

Last modified Tuesday, 14-Mar-2017 22:05:19 EDT