Fundamentals of Computer Algorithms Horowitz and Sahni, Computer Science Press, 1978
Page 97.
22. [T. Gonzalez]
Design a symbol table representation which allows one to search, insert and delete an identifier X in O(1) time. Assume that X {1,m} is integer valued that m + n units of space are available where n is the number of insertions to be made. (Hint: use two arrays A(1:n) and B(1:m) where A(i) will be the ith identifier inserted into the table. If X is the ith identifier inserted then B(X) = i). Write algorithms to search, insert, and delete identifiers. Note that you cannot initialize either A or B to zero as this would take O( m + n ).
22. [T. Gonzalez]
let S={x1, ..., xn} and T = {y1, ..., yr} be two sets. Assume 1 < xi < m,
1 < i < n, and
1 < yi < m,
1 < i < r. All xis and yis are integers. Using the idea of exercise 22 write an algorithm to determine if S is contained in T. Your algorithm should work in O(n + r) time. Since S is equal to T iff S is contained in T and T is contained in S, this implies that one can determine in linear time if two sets are equal. How much space is needed by your algorithm?