An Optimal Strategy for Algorithmic Debugging

Abstract—Algorithmic debugging is a technique that uses an internal data structure to represent computations and ask about their correctness. The strategy used to explore this data structure is essential for the performance of the technique. The most efficient strategy in practice is Divide and Query that, until now, has been considered optimal in the worst case. In this paper we first show that the original algorithm is inaccurate and moreover, in some situations it is unable to find all possible solutions, thus it is incomplete. Then, we present a new version of the algorithm that solves these problems. Moreover, we introduce a counterexample showing that Divide and Query is not optimal, and we propose the first optimal strategy for algorithmic debugging with respect to the number of questions asked by the debugger. Index Terms—Algorithmic Debugging, Divide and Query I