Review Exercises (Set C)

  1. 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;
    }
    

  2. 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?
  3. Use the graph whose adjacencies are given below to answer questions (a)-(c)
    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
    
    1. Identify the order in which the vertices are visited under a depth-first search, starting at 0.
    2. Identify the order in which the vertices are visited under a breadth-first search, starting at 0.
    3. Identify the shortest path, as found by the breadth-first search in (b) from vertex 0 to vertex 4.
  4. Which graph representation, adjacency list or adjacency matrix, is preferred for large, sparse graphs?

  5. Which data structure, queue or stack, can be used for a (non-recursive) depth-first search algorithm for a graph?

  6. What is an admissible heuristic?

  7. 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?

    1. $h(m) \le 1$
    2. $h(m) = 1$
    3. $h(m) \ge 1$
    4. there is no way to know anything about the value of $h(m)$.
  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

    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)
    
  9. 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
    
  10. A neural network is designed in the following way. There are two input neurons, A and B with input values (0.1 and 0.7, respectively). 2 hidden neurons, $\alpha$ and $\beta$, and one output neuron $\gamma$. The initial weights are given by the following table: $$\begin{array}{l} w_{A \alpha} = 0.1\\ w_{A \beta} = 0.3\\ w_{B \alpha} = 0.5\\ w_{B \beta} = 0.2\\ w_{\alpha \gamma} = 0.2\\ w_{\beta \gamma} = 0.1 \end{array}$$ If the target output is $1$ (and the learning rate is $1$), find the updated weights after one "training pass" on this network. Also, how much closer was the network's output to the target after the training pass?

Answers

  1. It "masks off" the sign bit of the hashCode, ensuring that the result is a non-negative integer (recall array indices are always non-negative)
  2. 7
    1. 0 7 1 2 4 6 5 3
    2. 0 7 5 2 1 6 4 3
    3. 0 $\rightarrow$ 7 $\rightarrow$ 4
  3. adjacency list
  4. stack
  5. An admissible heuristic is a function that provides an estimate -- but never an overestimate -- of the distance (or cost) to get from a given node to a desired destination node.
  6. c
  7.  
    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
    
  8.  
    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
    
  9. $$\begin{array}{l} w_{A \alpha} = 0.1007326\\ w_{A \beta} = 0.3004547\\ w_{B \alpha} = 0.5051282\\ w_{B \beta} = 0.2031829\\ w_{\alpha \gamma} = 0.2668\\ w_{\beta \gamma} = 0.16152 \end{array}$$ The network initially produced an output of $0.5429$. After the training, it produced an output of approximately $0.56097$, so after the training the output was approximately 0.01807 closer to the target.