A bit vector is simply an array of bits 0s and 1s A bit vect

A bit vector is simply an array of bits (0s and 1s). A bit vector of length m takes much less space than an array of m pointers. Describe how to use a bit vector to represent a dynamic set of distinct elements with no satellite data. Provide pseudocode for the three common dictionary operations: search, insert and delete, all of which should run in O (1) time. Explain why

Only asnwer Bold text of the question please. Thank You

Solution

If no satellite data (value associated with a key) needs to be stored, then we can create a bit vector of size m, where m = largest element we can store. Each index in the bit array is analogous to the element. If element is present then the value at that specific index is 1 else it is 0. That way all the dictionary operations (Search, Insert and Delete) will run in O(1) time.

If the key need not be unique then we can implement a direct address table using Hashing by Chaining. Against each duplicate key, there can be a linked list node containing satellite data. This can be a doubly linked list.