A note on unscrambling address lines

Abstract

A writer stores some data in memory accessible via address lines. If an adversary permutes the address lines after the writer leaves the message, then how can a reader find the permutation? This is the so-called unscrambling address lines problem of Broder et al. [SODA'99, 1999, pp. 870-871]. By a divide-and-conquer approach, we give a very simple algorithm to recover the permutation. Our method is much easier to understand than Broder et al.'s previous ad hoc solution. (C) 2002 Elsevier Science B.V. All rights reserved.