# Review Exercises (Set C2)

1. Complete the method hash(String s) below so that it produces a hash value in the following way: Using Horner's method, treat $s$ as an $n$-digit base-$b$ integer, compute the remainder that results when dividing that number by an integer $m$. (You may assume m and b have been previously defined as static constants.)

public int hash(String s) {
}

2. Suppose a hash function hash(char key) is such that the below code prints: 4 5 10 4 14 6 4.

char[] keys = {'a', 'c', 'e', 'h', 'r', 's', 'x'};
for (int i = 0; i < keys.length; i++) {
System.out.print(hash(keys[i] + " ");
}


Values associated with keys 's', 'e', 'a', 'r', 'c', 'h', 'x' are inserted into a hash table of size $16$ in that order. Show the keys and their positions in the array of bags that make up the hash symbol table presuming the hashing is done with separate chaining.

3. Use the graph whose adjacencies are given below to answer questions (a)-(c)

1 | 7 3
2 | 5 3 4
3 | 6 2 1
4 | 7 8 2
5 | 2 8 6
6 | 3 8 5
7 | 4 8 1
8 | 4 7 5 6


1. Identify the order in which vertices are visited with a depth-first search starting at vertex $1$.
2. Identify the order in which vertices are visited with a breadth-first search starting at vertex $1$.
3. Identify the shortest path, as found by the breadth-first search from $1$ to $5$.
4. Suppose we denote the number of vertices of a graph by V and the number of edges by E. What is the cost proportional to as a function of V and E for the space needed to store the graph for each of the following representations?

1. List of Edges
5. What data structure – a queue or a stack – can be used to implement a breadth-first search?

6. What is a consistent heuristic function?

7. Suppose a graph is created where each vertex is associated with one of the following words: "SEAL, BALL, SELL, BELL, TELL, TALL, TEAL, FELL, HEAL, HELL, HALL". Two vertices are connected by an edge if and only if the word associated with one vertex can be changed into the word associated with the other vertex by altering only one letter. (So, for example, TELL and FELL are adjacent, but TELL and BALL are not.) Every edge has weight 1. In seeking to find the shortest path from the vertex associated with the word "SEAL" to a goal vertex associated with the word "BALL", the A* algorithm is used. The heuristic function chosen, when applied to the vertex associated with "SEAL", yields an estimated cost of 5. Is the heuristic admissible? Explain why or why not.

8. Show the result of the trace of Dijkstra's shortest path algorithm on the directed, edge-weighted graph whose edge-list representation and resulting adjacency-lists representation are described below, starting from vertex 0. (That is to say, show the state of the distTo[] and edgeTo[] arrays and the values on the priority queue after each call to relax())

5
0 1 10.0           0: 0->1 0->4
0 4 5.0            1: 1->2 1->4
1 2 1.0            2: 2->3
1 4 2.0            3: 3->2 3->0
2 3 4.0            4: 4->1 4->2 4->3
3 2 6.0
3 0 7.0
4 1 3.0
4 2 9.0
4 3 2.0

9. Shade and label with consecutive letters the edges of the minimal spanning tree found by the lazy version of Prim's algorithm, where the initial vertex considered is vertex1. (So, the first edge found by the algorithm should be labeled "A", the second edge found should be labeled "B", the third "C", and so on...)

10. For any given cut of a weighted tree, explain why a minimal spanning tree must contain a minimal weight crossing edge for that cut.

11. Construct a perceptron that mimics a NAND gate and use it to find and draw a network of perceptrons that will output A || B for inputs A and B