CSC 311: Data Structures

(Fall 2007)

 

Assignment 3: Chapters 7 through 9

Due by November 8, Thursday, 2007

 

 

  1. Priority Queue
    1. Adaptor design pattern: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable. (Hint: the instance variable can be used as a priority generator based on timestamp)
    2. Algorithm design: Describe in detail an implementation of a priority queue based on a sorted array. Show that this implementation achieves O(1) time for operations min and removeMin and O(n) time for operation insert.

 

  1. Heap-sort
    1. Illustrate the execution of the heap-sort algorithm on the following input sequence: 2, 5, 16, 4, 10, 23, 39, 18, 26, 15.
    2. Show that the sum Sni=1logi, which appears in the analysis of heap-sort, is W(nlogn).

 

  1. Map and Search Table
    1. Describe how to use a map to implement the dictionary ADT, assuming that the user may attempt to insert entries with the same key.
    2. Design a variation of binary search for performing operation findAll(k) in a dictionary implemented with an ordered search table, and show that it runs in time O(logn + s), where n is the number of elements in the dictionary and s is the size of the iterator returned.

 

  1. Hash Table: Draw the 11-entry hash table that results from using the hash function, h(i)=(2i+5) mode 11, to hash the ksys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5, assuming collisions are handled by
    1. chaining;
    2. linear probing;
    3. quadratic probing, up to the point where the method fails;
    4. double hashing using the secondary hash function h'(k) = 7 - (k mod 7).