Offline Searching Let I = i₁,..., upto n be a sequence of N instructions. Each instruction i, is of the form (type,,x;)where type, € {insert, delete, search} and x, is a number. Given a sequence I of instructions, the offline search problem is to compute the sequence of results of the search instructions in I assuming that the instructions are applied sequentially on an initially empty set. More precisely, define S, to be the result of applying instructionsi₁,..., i, to an initially empty set. If instruction i, = (search, x,) and x, € S, the result of i, should be "yes"and otherwise the result should be "no". The output of the offline search problem for I is the sequence of results of the search instructions in I. We are interested in algorithms for the offline search problem in the external memory model of computation.1 Example Consider the sequence of instructions I = (insert, 5), (insert, 10), (search, 5), (delete, 5), (search, 5), (delete, 10) (search, 5), (search, 10). Show the sequence of results of the search instructions in I.

Fig: 1