A. Pelc, Weakly adaptive comparison searching,
Theoretical Computer Science 66 (1989), pp. 105-111.
A. Pelc, Weakly adaptive comparison searching,
Theoretical Computer Science 66 (1989), pp. 105-111.
Abstract:
We consider schemes of discrete search in the set {1, ..., n} using only comparison queries, i.e., those of the form `` x < a?''. Such a scheme is called i-adaptive if questions may be stated in i series, so that answers are obtained after each series but not between particular questions in it. We describe a worst-case optimal algorithm of i-adaptive search and determine its complexity. The latter turns out to be in1/i, where i may be a function of n. We also consider the closely related version of continuous search with a given error bound.
A. Pelc, Detecting a counterfeit coin with unreliable weighings,
Ars Combinatoria 27 (1989), pp. 181-192.
Abstract:
We provide a worst case shortest procedure to find one counterfeit heavier coin among identically looking coins when a beam balance can be used and at most one weighing result can be erroneous. The exact minimal number of weighings is shown. Its asymptotic behaviour for n coins is log3n +O (log log n).
J. Czyzowicz, D. Mundici, A. Pelc, Ulam's searching game with lies,
Journal of Combinatorial Theory, Series A, 52 (1989), pp. 62-76.
Abstract:
We determine the minimal number of yes-no queries sufficient to find an unknown integer between 1 and 2n, if at most two of the answers may be erroneous.
A. Pelc, Detecting errors in searching games,
Journal of Combinatorial Theory, Series A, 51 (1989), pp. 43-54.
Abstract:
We consider two-person searching games handling erroneous information. The Responder selects a number from {1, ..., n}, unknown to the Questioner, who has to find it asking yes-no questions. The Responder may lie up to k times during the entire search. In the first game the Questioner wins if he finds the unknown number or if he can prove that some answers were false. In the second game he also needs to determine the number of lies if they occurred. We study optimal winning strategies of the Questioner and determine their lengths. The results are compared to those about the minimal length of a k-error detecting code of given size.
A. Pelc, Searching with known error probability,
Theoretical Computer Science 63 (1989), pp. 185-202.
Abstract:
We study the problem of interactive searching in a set of numbers, using comparison queries, under the assumption that each answer can be erroneous with a constant probability p and that a given reliability 0 < q < 1 of the result is required. The search is considered in three versions: continuous (the search space is the interval [0, 1] and the unknown real x has to be found with a given accuracy 1/n, discrete bounded (x is an element of {1, ..., n}) and discrete unbounded (the unknown number n can be any positive integer). We prove that in all cases the search is feasible for any n and q iff p is different from 1/2. For such p, an O(log n) searching algorithm is given in the continuous case and O(log2n) algorithms in the discrete bounded and unbounded cases. For p < 1/3 or p > 2/3, O(log n) algorithms are given in each version of search.