S is a set of at most n elements, where n is given. Each element has a unique key in the range [0...n-1]. (i.e. no 2 different elements have the same key) Find a data structure of size O(n), that supports the following operations in the given times: Operation Time Init(n) Initialize S (S is an empty set at the beginning) O(n) isElement(k) Check if S has an element whose key equals to k O(1) Insert(x) Add element x to S O(1) Remove(k) Remove element whose key equals to k O(1) isEmpty() Check if S is empty O(1) Check if S contains all the elements whose keys are hasAll O(1) in the range [0...n-1] Solution: (Direct Addressing) : Array A[1..n] of pointers to elements. if A[k] == null, the element whose key is k is not in S. count = number of elements in S Init (n) for (i=0 ; i<n ; i++) A[i] = null; count = 0; Remove (k) If(isElement (k){ isElement (k) A[k] = null; return (A[k] != null); count--; } Insert (x) isEmpty () If(!isElement (x.key){ return (count == 0); A[x.key] = x; hasAll () count++; return (count == n); } Question 2 Suggest 2 ways to implement a Queue using 2 Stacks. Solution: The queue/stack is abstract, meaning the implementation isn't known, only the interface. In order to implement a queue we need to implement the following methods:
S is a set of at most n elements, where n is given. Each element has a unique key in the range [0...n-1]. (i.e. no 2 different elements have the same key) Find a data structure of size O(n), that supports the following operations in the given times: Operation Time Init(n) Initialize S (S is an empty set at the beginning) O(n) isElement(k) Check if S has an element whose key equals to k O(1) Insert(x) Add element x to S O(1) Remove(k) Remove element whose key equals to k O(1) isEmpty() Check if S is empty O(1) hasAll Check if S contains all the elements whose keys are in the range [0...n-1] O(1) Solution: (Direct Addressing) : Array A[1..n] of pointers to elements. if A[k] == null, the element whose key is k is not in S. count = number of elements in S Init (n) for (i=0 ; i<n ; i++) A[i] = null; count = 0; isElement (k) return (A[k] != null); Insert (x) If(!isElement (x.key){ A[x.key] = x; count++; } Remove (k) If(isElement (k){ A[k] = null; count--; } isEmpty () return (count == 0); hasAll () return (count == n); Question 2 Suggest 2 ways to implement a Queue using 2 Stacks. Solution: The queue/stack is abstract, meaning the implementation isn't known, only the interface. In order to implement a queue we need to implement the following methods: