counterfeit_detection

counterfeit_detection, a Python 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.

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 a Python version.

Related Data and Programs:

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.py, the source code.
• counterfeit_detection.sh, runs all the tests.
• counterfeit_detection.txt, the output file.