2 Dictionary Abstract Datatype (16 points) Recall that the dictionary abstract data type stores a collection...

Transcribed Image Text:

2 Dictionary Abstract Datatype (16 points) Recall that the dictionary abstract data type stores a collection of keys, and supports the operations insert, delete, and search. If the keys are totally ordered, then it can also support FindMin and FindMax. Suppose there are 1000 elements, each of which takes 16 bytes to store. Each element contains a key-value pair. Moreover, each pointer takes 4 bytes. In each case, (1) briefly describe the data structure and explain how the operations are imple- mented, and (2) analyze the exact space used (in bytes). (a) (4 pt) Suppose all the elements are given at the beginning, and there is no insertion or deletion afterwards. Only the search operation will be used later, and a good guarantee on the worst case search time is required. (b) (4 pt) Elements will be inserted and deleted frequently. The average running time for insert, delete and search is O(1), and on average at most. 5 elements are accessed for each operation. (c) (4 pt) All operations insert, delete and search are used frequently. A guarantee on the worst case running time (in terms of number of elements accessed) is needed. (d) (4 pt) Each key is an integer in (1,2,..., 100}. Each insertion or deletion has worst-case O(1) time. You may assume that each key appears at least once. Moreover, FindRange[a..b] needs to return all elements whose keys are in [a..b], where the running time is proportional to the number of elements returned. 2 Dictionary Abstract Datatype (16 points) Recall that the dictionary abstract data type stores a collection of keys, and supports the operations insert, delete, and search. If the keys are totally ordered, then it can also support FindMin and FindMax. Suppose there are 1000 elements, each of which takes 16 bytes to store. Each element contains a key-value pair. Moreover, each pointer takes 4 bytes. In each case, (1) briefly describe the data structure and explain how the operations are imple- mented, and (2) analyze the exact space used (in bytes). (a) (4 pt) Suppose all the elements are given at the beginning, and there is no insertion or deletion afterwards. Only the search operation will be used later, and a good guarantee on the worst case search time is required. (b) (4 pt) Elements will be inserted and deleted frequently. The average running time for insert, delete and search is O(1), and on average at most. 5 elements are accessed for each operation. (c) (4 pt) All operations insert, delete and search are used frequently. A guarantee on the worst case running time (in terms of number of elements accessed) is needed. (d) (4 pt) Each key is an integer in (1,2,..., 100}. Each insertion or deletion has worst-case O(1) time. You may assume that each key appears at least once. Moreover, FindRange[a..b] needs to return all elements whose keys are in [a..b], where the running time is proportional to the number of elements returned.

Answer rating: 100% (QA)

2 ANSWER GIVEN THAT a and b Hash Table Insertiondeletionsearch Average complexity constant ie O1 Wor... View the full answer