Review Exercises (Set C)

  1. Recalling that x.hashCode() returns a 32-bit integer, what is the purpose of the "x.hashCode() & 0x7fffffff" in the below hash() method? 

    private int hash(Key x) {
   return (x.hashCode() & 0x7fffffff) % M;
}

    It forces the leading bit of the hash code produced to be 0, thus producing a positive integer.

  2. The following two questions concern the insertion of the letters of the word "HASHBROWN" as keys into a hash table. The hash codes for these letters are given below. 

    H : 72
A : 65
S : 83
H : 72
B : 66
R : 82
O : 79
W : 87
N : 78

    1. Show the state of the resulting hash table after these letters have been inserted (in order) into an initially empty hash table using an array of size 7 and separate chaining to resolve collisions. 

      Resulting Hash Table:
0 : -
1 : N
2 : OAH
3 : WB
4 : -
5 : R
6 : S

    2. Show the state of the resulting hash table after these letters have been inserted (in order) into an initially empty hash table using linear probing to resolve collisions. 

      Resulting Hash Table:
0 : -
1 : A
2 : B
3 : S
4 : R
5 : -
6 : -
7 : W
8 : H
9 : -
10 : -
11 : -
12 : -
13 : -
14 : N
15 : O

  3. Given the following adjacency list, draw the graph so described, and then give the edges of the breadth-first paths tree found with source 0, in the order they are added to the tree. Finally, give the shortest path, as found by the breadth-first traversal in question between 0 and 6.

    7 vertices, 10 edges 
0: 5 1 
1: 4 0 
2: 5 6 4 3 
3: 5 2 
4: 6 2 1 5 
5: 0 2 3 4 
6: 4 2 

    Edges of Breadth-first Paths Tree:
0-5
0-1
5-2
5-3
5-4
2-6

Shortest path between vertices 0 and 6:
0-5-2-6

  4. Given the following adjacency list, draw the graph so described, and then give the edges of the depth-first paths tree found with source 0, in the order they are added to the tree.

    7 vertices, 10 edges 
0: 2 1 4 
1: 0 5 3 
2: 0 6 4 
3: 1 4 
4: 0 6 2 3 
5: 6 1 
6: 5 2 4 

    Edges of Depth-first Paths Tree:
0-2
2-6
6-5
5-1
1-3
3-4

  5. Given the edge-weighted digraph described below, list the edges, in order discovered, in accordance with Dijkstra's algorithm, of the tree that describes the shortest paths to vertex 0. Also indicate, in order discovered, any edge relaxations that were made in the process of conducting Dijkstra's algorithm. 

    7 vertices, 20 edges 
0: 0--0.71-->4  0--0.03-->6  0--0.57-->1  0--0.59-->5  0--0.94-->2  
1: 1--0.14-->2  1--0.13-->5  1--0.42-->6  
2: 2--0.86-->3  2--0.48-->4  
3: 3--0.32-->2  3--0.11-->1  
4: 4--0.75-->6  4--0.65-->0  4--0.05-->1  
5: 5--0.67-->0  5--0.92-->1  5--0.87-->6  
6: 6--0.14-->2  6--0.01-->1 

    Relaxations of distance to 0:
4: ∞ to 0.71
6: ∞ to 0.03
1: ∞ to 0.57
5: ∞ to 0.59
2: ∞ to 0.94
2: 0.94 to 0.17
1: 0.57 to 0.04
5: 0.59 to 0.17
3: ∞ to 1.03
4: 0.71 to 0.65

Edges of Shortest Paths Tree:
6--0.01-->1
6--0.14-->2
2--0.86-->3
2--0.48-->4
1--0.13-->5
0--0.03-->6

  6. Given the edge-weighted graph described below, list the edges, in order discovered, in accordance with the "lazy" version of Prim's algorithm, of the minimal spanning tree for the component containing the vertex 0. Also, list all ineliglbe edges encountered in the course of that algorithm, in the order they are found. 
    7 vertices, 10 edges 
0: 0-(0.23)-1 3-(0.43)-0 
1: 1-(0.99)-5 1-(0.16)-3 0-(0.23)-1 
2: 6-(0.31)-2 2-(0.92)-5 
3: 1-(0.16)-3 3-(0.22)-4 5-(0.87)-3 3-(0.43)-0 
4: 3-(0.22)-4 6-(0.44)-4 
5: 1-(0.99)-5 5-(0.94)-6 2-(0.92)-5 5-(0.87)-3 
6: 6-(0.31)-2 5-(0.94)-6 6-(0.44)-4

    Ineligible Edges Encountered:
3-(0.43)-0
2-(0.92)-5
5-(0.94)-6
1-(0.99)-5

Edges of Minimal Spanning Tree:
0-(0.23)-1
1-(0.16)-3
3-(0.22)-4
6-(0.44)-4
6-(0.31)-2
5-(0.87)-3

  7. Which graph representation, adjacency list or adjacency matrix, is preferred for large, sparse graphs?

    An adjacency list will be much preferred. The adjacency matrix cost more in terms of both storage and finding adjacent vertices to a given vertex.

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

    Stack

  9. Supposing a class Graph has been created with a method adj(int v) that returns an Iterable collection of the adjacent vertices (each represented as an int) to vertex $v$, complete the class BreadthFirstTraversal below, so that the method bfs(g,s) prints the vertices in order they are visited during a breadth-first search: 

    public class BreadthFirstTraversal {

    // any needed instance variables here...
 
    public BreadthFirstTraversal(Graph g, int source) {
   
        // your code here...

    }
    
    private void bfs(Graph g, int s) {

        // your code here...

    }

    public class BreadthFirstTraversal {

    private boolean visited[];
    QueueArray q = new QueueArray();

    public BreadthFirstTraversal(Graph g, int source) {
        visited = new boolean[g.numVertices()];
        bfs(g,source);
    }

    private void bfs(Graph g, int s) {
        visited[s] = true;
        q.enqueue(s);
        while (!q.isEmpty()) {
            int v = q.dequeue();
            System.out.println(v);
            for (int w : g.adj(v)) {
                if (!visited[w]) {
                   visited[w] = true;
                   q.enqueue(w);
                }
            }
        }
    }