Exercises 11.1

11.1-1 Suppose that a dynamic set S is represented by a direct-address table T of length m. Describe a procedure that finds the maximum element of S. What is the worst-case performance of your procedure?

Solution: Maintain a variable "max" with the lowest possible value.Now iterate through each element in the set and check if the current element is greater than the max. If it is then current element becomes max else move to the next element. This way keep iterating over all the elements in the set. Worst case time complexity is O(m)

11.1-2 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. Dictionary operations should run in O(1) time.

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.

11.1-3 Suggest how to implement a direct-address table in which the keys of stored elements do not need to be distinct and the elements can have satellite data. All three dictionary operations (INSERT, DELETE, and SEARCH) should run in O(1) time. (Don’t forget that DELETE takes as an argument a pointer to an object to be deleted, not a key.)

Solution: 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.

  • Insert operation will be O(1) because each time, new node will be added to the head of the linked list.
  • Delete operation will be O(1) because the address to the node will be given.
  • Search operation will be O(1) because the
    • Load Factor (α) = # elements per slot/# slots in table
    • This figure will be constant so, the Search in case of duplicate keys will still be O(1)

11.1-4 We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a directaddress dictionary on a huge array. Each stored object should use O(1) space; the operations SEARCH, INSERT, and DELETE should take O(1) time each; and initializing the data structure should take O(1) time. (Hint: Use an additional array, treated somewhat like a stack whose size is the number of keys actually stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.)

Solution: