Hashing and Breadth-First Search

Exercise 1: Hashing (6 points)

Suppose that the following keys are inserted in some order into an initially empty linear-probing hash table of size 7 (assuming no resizing), using the following table of hash values:

Key	Hash
A	5
B	2
C	5
D	1
E	4
F	1
G	3

1. Give the contents of the linear-probing array if the keys are inserted in alphabetical order: A, B, C, D, E, F, G. Report the resulting array in your submission, for example as a row indexed from 0 to 6.
2. Which of the following could be the contents of the linear-probing array if the keys are inserted in some other order?

Candidate 1
0	1	2	3	4	5	6
A	F	D	B	G	E	C

Candidate 2
0	1	2	3	4	5	6
F	A	D	B	G	E	C

Candidate 3
0	1	2	3	4	5	6
C	A	B	G	F	E	D

Choose the best answer.

1. 1 only
2. 1 and 2 only
3. 1 and 3 only
4. 1, 2, and 3
5. None

Exercise 2: Breadth-first search (16 points)

1. Run breadth-first search on the graph below, starting at vertex A. Assume the adjacency sets are in sorted order. For example, when exploring vertex F, the algorithm considers the edge F-C before F-D, F-E, or F-H.

2. Consider two vertices x and y that are simultaneously on the FIFO queue at some point during the execution of breadth-first search from s in an undirected graph. Which of the following are true?
   1. The number of edges on the shortest path between s and x is at most one more than the number of edges on the shortest path between s and y.
   2. The number of edges on the shortest path between s and x is at least one less than the number of edges on the shortest path between s and y.
   3. There is a path between x and y.