Problem definitions Implicit model. All operations from the ram It is not allowed to create words only to move them All n words have to be in continuous positions Often it is assumed that all elements are distinct Fundamental trick; encode a bit in a pair of elements X 0, if X=min(x y) 1, if X=max(x,y) earmarks undforskringsfond Casper Kejlberg-Rasmussen maDalgo- 3/16 UNIVERSIT CENTER FOR MASSIVE DATA ALGORITHMICSCasper Kejlberg-Rasmussen 3/16 Problem Definitions ▪ Implicit model: ▪ All operations from the RAM ▪ It is not allowed to create words, only to move them ▪ All n words have to be in continuous positions ▪ Often it is assumed that all elements are distinct ▪ Fundamental trick: encode a bit in a pair of elements ... 1 n x y b b= 0, if x=min(x,y) 1, if x=max(x,y)