counterfeit_detection

counterfeit_detection an Octave code which considers problems in which one or more counterfeit coins are to be identified by the fact that they do not have the standard weight.

Unfortunately, octave needs the packages linprog() and statistics(), but my version of octave is too old to support them.

Methods include:

• brute force: weigh every coin and report those with bad weight;
• combinatorial: assume there is only 1 bad coin, and that the number of coins is 2^n-1. carry out n weighings to determine the bad coin.
• compressed sensing: weigh a certain number of random subsets of the coins and solve an underdetermined linear system minimizing the l1 norm.

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

counterfeit_detection is available in a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

counterfeit_detection_test

Reference:

1. Kurt Bryan, Tanya Leise,
   Making do with less: an introduction to compressed sensing,
   SIAM Review,
   Volume 55, Number 3, September 2013, pages 547-566.

Source Code:

• counterfeit_detection_brute.m, brute force approach to finding counterfeit coins;
• counterfeit_detection_combinatorial.m, combinatorial approach to finding a counterfeit coin;
• counterfeit_detection_compressed.m, compressed sensing approach to finding countereit coins.
• ksub_random2.m, selects a random subset of size K from a set of size N.