𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The average complexity of a coin-weighing problem

✍ Scribed by L. Alonso; P. Chassaing; R. Schott

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
511 KB
Volume
9
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

Given a set of n coins, some of them weighing H , the others weighing h , h < H , we prove that to determine the set of heavy coins, an optimal algorithm requires an average of

probabilities of being light and heavy. A simple quasi-optimal algorithm is described.

Similar results are derived for the majority problem. 0

πŸ“œ SIMILAR VOLUMES

The complexity of the network design pro
The complexity of the network design problem
✍ D. S. Johnson; J. K. Lenstra; A. H. G. Rinnooy Kan πŸ“‚ Article πŸ“… 1978 πŸ› John Wiley and Sons 🌐 English βš– 278 KB
On the complexity of the pancake problem
On the complexity of the pancake problem
✍ Fuxiang Yu πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 249 KB

## Abstract We study the computational complexity of finding a line that bisects simultaneously two sets in the two‐dimensional plane, called __the pancake problem__, using the oracle Turing machine model of Ko. We also study the basic problem of bisecting a set at a given direction. Our main resul

Average-case complexity of shortest-path
Average-case complexity of shortest-paths problems in the vertex-potential model
✍ Colin Cooper; Alan Frieze; Kurt Mehlhorn; Volker Priebe πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 146 KB πŸ‘ 2 views

We study the average-case complexity of shortest-paths problems in the vertexpotential model. The vertex-potential model is a family of probability distributions on complete directed graphs with arbitrary real edge lengths, but without negative cycles. We show that on a graph with n vertices and wit