Hash Tables

(These questions refer to examples from chapter 12 of the course notes.) From chapter 12, this is a description of Amy's hash function assuming an initial table size of 6:

"Amy uses an interesting fact. If she selects the third letter of each name, treating the letter as a number from 0 to 25, and then Mods the number by 6, each name yields a different number"

1. When Alan wishes to join the circle of six friends, why can't Amy simply increase the size of the table to seven? 2. Amy's club has grown, and now includes the following members:

Abel Abigail Abraham Ada Adam Adrian Adrienne Agnes Albert Alex Alfred Alice

a. Find what value would be computed by Amy's hash function for each member of the group, BEFORE modding by the table size. b. Now, assume we use Amy's hash function and assign each member to a bucket by simply modding the hash value (obtained from part a) by the number of buckets. Determine how many elements would be assigned to each bucket (assume hashing with chaining) for a hash table of size 6. Do the same for a hash table of size 13. c. What are the load factors of these two tables? 3. In searching for a good hash function over the set of integer values, one student thought he could use the following:

int index = (int) cos(value); // Cosine of 'value'

What was wrong with this choice? 4. Can you come up with a perfect hash function for the names of days of the week? The names of the months of the year? Assume a table size of 10 for days of the week and 15 for names of the months. In case you cannot find any perfect hash functions, we will accept solutions that produce a small number of collisions (< 3). 5. The function containsKey() can be used to see if a dictionary contains a given key. How could you determine if a dictionary contains a given value? What is the complexity of your procedure? Graphs (These questions refer to examples from chapter 13 of the course notes.) Describe the following graph as both an adjacency matrix and an edge list: graph (Links to an external site.) Construct a graph in which a depth first search will uncover a solution (discover reachability from one vertex to another) in fewer steps than will a breadth first search. You may need to specify an order in which neighbor vertices are visited. Construct another graph in which a breadth-first search will uncover a solution in fewer steps. Complete Worksheet 41 (2 simulations). Show the content of the stack, queue, and the set of reachable nodes. Complete Worksheet 42 (1 simulation). Show the content of the priority queue and the cities visited at each step. Why is it important that Dijkstra's algorithm stores intermediate results in a priority queue, rather than in an ordinary stack or queue? How much space (in big-O notation) does an edge-list representation of a graph require? For a graph with V vertices, how much space (in big-O notation) will an adjacency matrix require? Suppose you have a graph representing a maze that is infinite in size, but there is a finite path from the start to the finish. Is a depth first search guaranteed to find the path? Is a breadth-first search? Explain why or why not.