Q09

Suggest a data structure for representing a subset $S$ of integers from $1$ to $n$. Following operations on the set $S$ are to be performed in constant time (independent of cardinality of $S$).

$$\begin{array}{cll} \text{i.}& \text{MEMBER $(X):$} & \text{Check whether $X$ is in the set $S$ or not} \\ \text{ii.} & \text{FIND-ONE $(S):$} & \text{If $S$ is not empty, return one element of the set $S$}\\ & & \quad\text{(any arbitrary element will do)} \\ \text{iii.} & \text{ADD $(X):$} & \text{Add integer $X$ to set $S$} \\ \text{ii.} & \text{DELETE $(X):$} & \text{Delete integer $X$ from $S$} \end{array}$$

Give pictorial examples of your data structure. Give routines for these operations in an English like language. You may assume that the data structure has been suitable initialized. Clearly state your assumptions regarding initialization.