7 In-Place Dictionaries Let S be a set of n integers. Recall that a dictionary supports...

Transcribed Image Text:

7 In-Place Dictionaries Let S be a set of n integers. Recall that a dictionary supports the following operations. • member(x): determine if x € S. • insert(x): set S = SU{x}. • delete(x): set S = S\{x}. We consider in-place dictionaries. Solve the following exercises. 7.1 [w] Suppose that we only want to support member. Give a in-place data structure that supports member in O(logn) time. Hint: binary search. 7.2 Let A be a rotated sorted array of length n containing the integers in S, i.e., A is a circular shift of the sorted array of the integers in S. Show how to search in A in O(logn) time with an in-place. Assume that you cannot afford to store the circular shift. Hint: peaks. 7.3 [*] Show how implement an in-place dictionary that supports member in O(log n) time and insertions and deletions in O(√n log n) time. 7 In-Place Dictionaries Let S be a set of n integers. Recall that a dictionary supports the following operations. • member(x): determine if x € S. • insert(x): set S = SU{x}. • delete(x): set S = S\{x}. We consider in-place dictionaries. Solve the following exercises. 7.1 [w] Suppose that we only want to support member. Give a in-place data structure that supports member in O(logn) time. Hint: binary search. 7.2 Let A be a rotated sorted array of length n containing the integers in S, i.e., A is a circular shift of the sorted array of the integers in S. Show how to search in A in O(logn) time with an in-place. Assume that you cannot afford to store the circular shift. Hint: peaks. 7.3 [*] Show how implement an in-place dictionary that supports member in O(log n) time and insertions and deletions in O(√n log n) time.

Answer rating: 100% (QA)

the solution of this problem is given below Answer 71 Since binary search has a best case efficiency of O1 and worst case average case efficiency of O... View the full answer