How many questions are necessary and sufficient to guess an unknown number x in the set S = {1, 2, . . . , n}, by using only comparison questions, that is questions of the type “Is x \leq a?”, a ∈ S, when answers to questions are received with a delay of d time units and up to c of the answers can be lost, i.e., can not be received at all? We exactly solve this problem for all integers d \geq 0 and c = 1.
Binary Search with Delayed and Missing Answers
CICALESE, Ferdinando;VACCARO, Ugo
2003-01-01
Abstract
How many questions are necessary and sufficient to guess an unknown number x in the set S = {1, 2, . . . , n}, by using only comparison questions, that is questions of the type “Is x \leq a?”, a ∈ S, when answers to questions are received with a delay of d time units and up to c of the answers can be lost, i.e., can not be received at all? We exactly solve this problem for all integers d \geq 0 and c = 1.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
