Download pdf
The recovery time complexity of a coin weighing algorithm
- 1 Shanghai Shibei Senior High School
* Author to whom correspondence should be addressed.
Abstract
Given n identical-looking coins each with possible weight in {0, 1}, and a scale that can measure the weight of any arbitrary set of coins, the coin weighing problem studies how to find out the weight of every coin with as few weighing as possible. The algorithm in Lindström takes O(n/logn) non-adaptive weighings to determine the coins, which gives an O(logn) factor improvement compared with the naïve algorithm that measures each coin on its own. However, it is unclear that with the O(n/logn) queries, how long it takes to retrieve x. This paper is about establishing and further optimizing the naïve recovery time complexity of Lindström ‘s algorithm. The recovery time complexity here is defined as the time complexity to recover x given Dx under the RAM model, where D∈{0,1}^(m×n),, each row being a weighing query, is the Lindström query matrix. The brute force recovery algorithm has running time O(m2n), whereas our algorithm only takes O(mn). Finally, we run experiments to verify our results with the actual running time of the algorithm on various size of inputs
Keywords
Group testing, Coin Weighing Problem, Quantitative Group Testing
[1]. Lindström, B. (1971). On Möbius functions and a problem in combinatorial number theory. Canadian Mathematical Bulletin, 14(4):513-516.
[2]. Cantor, D. G. and Mills, W. H. (1964). Determination of a subset from certain combinatorial properties.
[3]. Bshouty, N. H. (2009). Optimal algorithms for the coin weighing problem with a spring scale. In COLT, volume 2009, page 82.
[4]. Bose, R. C. and Ray-Chaudhuri, D. K. (1960). On A class of error correcting binary group codes. Inf. Control., 3(1):68-79.
[5]. Gebhard, O., Hahn-Klimroth, M., Kaaser, D., and Loick, P. (2019). Quantitative group testing in the sublinear regime. CoRR, abs/1905.01458.
[6]. Karimi, E., Kazemi, F., Heidarzadeh, A., Narayanan, K. R., and Sprintson, A. (2019).
Cite this article
Wang,H. (2024). The recovery time complexity of a coin weighing algorithm. Theoretical and Natural Science,30,195-204.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of the 3rd International Conference on Computing Innovation and Applied Physics
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).