CS 410 Fall 99
Homework 4
Due Tuesday, November 16

Reading

Read CLR ch. 25, 26.1-3.

Written Exercises

1. CLR 10-1 p. 193.
2. CLR 12.3-1 p. 231.
3. CLR 12.4-1 p. 240.
4. CLR 23.1-6 p. 468.
5. Suppose we have n total elements divided into m sorted lists. Explain how to produce a single sorted list of all n elements in time O(n log m).
6. How could we lower the worst-case time for a hashtable with chaining to O(log n) where n is the number of elements in the table?  Why don't we care?
7. Say you wish to support the following operations on directed graphs:

   (i) exist(u,v) - test if edge (u,v) is in the graph
   (ii) insert(u,v) - insert edge (u,v)
   (iii) delete(u,v) - delete edge (u,v)
   (iv) out(u) - output all edges exiting vertex u
   (v) in(u) - output all edges entering vertex u.

   Let n be the number of vertices, m the number of edges, and outdegree(u) and indegree(u) the number of vertices leaving and entering vertex u, respectively.

   (a) Suppose you use an adjacency matrix to represent the graph. How much time does each operation require?
   (b) Suppose you use the adjacency list data structure as described in class. How much time does each operation require?
   (c) Design a data structure that combines the features of the adjacency list and adjacency matrix representations in which operations (i), (ii), and (iii) take time O(1) and operations (iv) and (v) take time O(outdegree(u)) and O(indegree(u)), respectively.

8. Prove that the set of all functions from {0,1,...,n-1} to {0,1,...,m-1} is universal.   Why is this an impractical choice for universal hashing?