Let In be the set of n integers {1, 2,...,n} where n is some power of...

  

Transcribed Image Text:

Let In be the set of n integers {1, 2,...,n} where n is some power of 2. Note that we can easily use an n-bit vector (i.e., an array of n bits) B[1..n] to maintain a subset S of In and perform the following three operations (where j is any integer in In) in constant time each: INSERT(): insert integer j into S. DELETE(): delete integer j from S. MEMBER(j): return true if je S, otherwise return false. Describe a data structure that supports all the above operations and also the following operation MAXIMUM: return the greatest integer in S such that: • The worst-case time complexity of operations INSERT(j), DELETE(j), and MAXIMUM is O(log n) each. The worst-case time complexity of MEMBER(j) is 0(1). • The data structure uses only O(n) bits of storage. Note that the binary representation of an integer i where 1 ≤ i ≤n takes (log n) bits. Assume that any pointer also takes (log n) bits. A solution that does not meet all the above requirements may not get any credit. HINT: Combine an n-bit vector with a complete binary tree, and avoid using pointers. a. Describe your data structure by drawing it for n = 8 and S = {1,2,6}, and by explaining this drawing briefly and clearly. Your drawing must be very clear. b. Explain how the operations INSERT(j), DELETE(j), and MAXIMUM are executed, and why they take O(log n) time in the worst-case. Be brief and precise. c. Explain how the operation MEMBER (j) is executed, and why it takes O(1) time in the worst-case. Be brief and precise. Let In be the set of n integers {1, 2,...,n} where n is some power of 2. Note that we can easily use an n-bit vector (i.e., an array of n bits) B[1..n] to maintain a subset S of In and perform the following three operations (where j is any integer in In) in constant time each: INSERT(): insert integer j into S. DELETE(): delete integer j from S. MEMBER(j): return true if je S, otherwise return false. Describe a data structure that supports all the above operations and also the following operation MAXIMUM: return the greatest integer in S such that: • The worst-case time complexity of operations INSERT(j), DELETE(j), and MAXIMUM is O(log n) each. The worst-case time complexity of MEMBER(j) is 0(1). • The data structure uses only O(n) bits of storage. Note that the binary representation of an integer i where 1 ≤ i ≤n takes (log n) bits. Assume that any pointer also takes (log n) bits. A solution that does not meet all the above requirements may not get any credit. HINT: Combine an n-bit vector with a complete binary tree, and avoid using pointers. a. Describe your data structure by drawing it for n = 8 and S = {1,2,6}, and by explaining this drawing briefly and clearly. Your drawing must be very clear. b. Explain how the operations INSERT(j), DELETE(j), and MAXIMUM are executed, and why they take O(log n) time in the worst-case. Be brief and precise. c. Explain how the operation MEMBER (j) is executed, and why it takes O(1) time in the worst-case. Be brief and precise.

Answer rating: 100% (QA)

The question provided involves designing a data structure that maintains a set S of integers from a finite set In 1 2 ldots n where n is a power of 2 ... View the full answer