Recalling that x.hashCode()
returns a 32-bit integer, what is the purpose of the "x.hashCode() & 0xfffffff
"?
private int hash(Key x) { return (x.hashCode() & 0x7fffffff) % M; }
Suppose a hash function hash(char key)
is such that the code below prints: 4 5 10 4 14 6
.
char[] keys = {'a', 'c', 'e', 'h', 'r', 's'}; for (int i = 0; i < keys.length; i++) { System.out.print(hash(keys[i] + " "); }Values associated with keys
's', 'e', 'a', 'r', 'c', 'h'
are inserted into a hash table of size $16$ in that order. At what position in the array (i.e., index) is the value associated with 'h'
inserted if the hashing is done with linear probing?
0 | 7 5 2 1 6 1 | 7 0 2 | 7 0 3 | 5 4 4 | 6 5 7 3 5 | 0 4 3 6 | 4 0 7 | 1 2 0 4
Which graph representation, adjacency list or adjacency matrix, is preferred for large, sparse graphs?
Which data structure, queue or stack, can be used for a (non-recursive) depth-first search algorithm for a graph?
What is an admissible heuristic?
Suppose $h$ is a consistent heuristic function, $n$ and $m$ are adjacent nodes, the cost to get to $m$ from $n$ is $5$, and $h(n) = 6$. Which of the following is true?
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
sample_edge_weighted_directed_graph.txt ======================================= 7 0 1 5.0 0 3 3.0 1 2 1.0 2 4 6.0 2 6 8.0 3 4 2.0 3 5 2.0 4 1 4.0 5 6 3.0 6 4 4.0 Adjacency-lists Representation ============================== 0 | (0->1,5.0) (0->3,3.0) 1 | (1->2, 1.0) 2 | (2->4, 6.0) (2->6, 8.0) 3 | (3->4, 2.0) (3->5, 2.0) 4 | (4->1, 4.0) 5 | (5->6, 3.0) 6 | (6->4, 4.0)
Show the result of the trace of of the lazy version of Prim's Algorithm as it finds the edges of the minimal spanning tree for the graph whose edge-list representation is given by the following, and where vertex 0 is the first vertex visited.
tiny_edge_weighted_graph.txt ============================ 8 4 5 .35 4 7 .37 5 7 .28 0 7 .16 1 5 .32 0 4 .38 2 3 .17 1 7 .19 0 2 .26 1 2 .36 1 3 .29 2 7 .34 6 2 .40 3 6 .52 6 0 .58 6 4 .93
extracted 0 from priority queue relaxed distTo[1] to 5.0 set edgeTo[1] to 0->1 inserted 1 in priority queue with dist=5.0 relaxed distTo[3] to 3.0 set edgeTo[3] to 0->3 inserted 3 in priority queue with dist=3.0 extracted 3 from priority queue relaxed distTo[4] to 5.0 set edgeTo[4] to 3->4 inserted 4 in priority queue with dist=5.0 relaxed distTo[5] to 5.0 set edgeTo[5] to 3->5 inserted 5 in priority queue with dist=5.0 extracted 1 from priority queue relaxed distTo[2] to 6.0 set edgeTo[2] to 1->2 inserted 2 in priority queue with dist=6.0 extracted 5 from priority queue relaxed distTo[6] to 8.0 set edgeTo[6] to 5->6 inserted 6 in priority queue with dist=8.0 extracted 4 from priority queue determined 4-1 is ineligible extracted 2 from priority queue determined 2-4 is ineligible determined 2-6 is ineligible extracted 6 from priority queue determined 6-4 is ineligible
Added 0 to mst vertices Added 0-7 to crossing edges priority queue Added 0-4 to crossing edges priority queue Added 0-2 to crossing edges priority queue Added 6-0 to crossing edges priority queue Added edge 0-7 to mst edges Added 7 to mst vertices Added 4-7 to crossing edges priority queue Added 5-7 to crossing edges priority queue Added 1-7 to crossing edges priority queue Added 2-7 to crossing edges priority queue Added edge 1-7 to mst edges Added 1 to mst vertices Added 1-5 to crossing edges priority queue Added 1-2 to crossing edges priority queue Added 1-3 to crossing edges priority queue Added edge 0-2 to mst edges Added 2 to mst vertices Added 2-3 to crossing edges priority queue Added 6-2 to crossing edges priority queue Added edge 2-3 to mst edges Added 3 to mst vertices Added 3-6 to crossing edges priority queue Added edge 5-7 to mst edges Added 5 to mst vertices Added 4-5 to crossing edges priority queue Added edge 4-5 to mst edges Added 4 to mst vertices Added 6-4 to crossing edges priority queue Added edge 6-2 to mst edges Added 6 to mst vertices 0-7 1-7 0-2 2-3 5-7 4-5 6-2