W2017 Lab 5

Ryerson University

Worth: 5%

Fake Coin Problem

Due: Monday March 20

Team Size

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 balance scale.

You can design an efficient algorithm which uses the scale to find the fake coin:

  1. 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.

  2. 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.
Hopefully you have recognized that since the problem is cut in half at each iteration, this is yet another wonderful algorithm of order log2n.

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
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

  1. The size of the problem is n = # of coins in coinpile

  2. The basic operation is a function call to the Weigh function.

  3. 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.

  4. 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. i.e. k=log2n.
    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

Lab Description

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 (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 In

This lab is a paper submission to be handed in at the Computer Science office.
  • Hand in a printout of your solution/marking sheet (docx or pdf).
  • 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

This page is maintained by Sophie Quigley (cps616@scs.ryerson.ca)
Last modified Tuesday, 14-Mar-2017 22:05:19 EDT