Exercise 9        Name __________________        Score __/ 19
Document last modified: 

  1. (2) Give the MAKE-SET procedure that when called by:

    for i ¬ 1 to 8 do MAKE-SET(xi)

    produces the data structure p where every xi is the only member and the representative of the set; and the data structure c, the number of elements in the set i:

    i 1 2 3 4 5 6 7 8
    p[i]|c[i] 1|1 2|1 3|1 4|1 5|1 6|1 7|1 8|1

     

  2. (7) Show the data structure that results and the answers returned by the following program.
    i 1 2 3 4 5 6 7 8
    Line 1 p[i]                
    Line 2 p[i]                
    Line 3 p[i]                
    Line 4 p[i]                
    Line 5 p[i]                
    Line 6 p[i]                

    Line 5 answer:           

    Line 6 answer:           

    1. for i ¬ 1 to 8 do MAKE-SET(xi)
    2. for i ¬ 1 to 7 by 2 do UNION(xi, xi+1)
    3. UNION(x1, x3)
    4. UNION(x1, x5)
    5. FIND-SET(x1)
    6. FIND-SET(x7)
    FIND-SET (x)
       if p[ x ] ¹ x then return FIND-SET ( p[ x ] )
       return x
    UNION (x, y)
       a ¬ FIND-SET (x)
       b ¬ FIND-SET (y)
       p[ a ] ¬ b          

     

  3. (6) For the following diagram below, give adjacency-matrix and questions a-g:

    1. V?                

    2. |V|?             

    3. |E|?             

    4. (A, B) Î E?             

    5. (A, A) Î E?             

    6. Out-degree of vertex A?                   

    7. In-degree of vertex C?             

      A B C D E F G
    A              
    B              
    C              
    D              
    E              
    F              
    G              

     

  4. (2) Show the d and p values that result from running the breadth-first search on the directed graph of Figure 22.2(a) using vertex 3 as the source.
      1 2 3 4 5 6
    p            
    d            
  5. (4) Show how DFS works for the following graph. Assume the for loop of lines 5-6 of the DFS procedure considers vertices in alphabetical order and assume that the adjacency list is ordered alphabetically. Show the discovery and finishing times for each vertex (d on the left and f on the right side of the node) and show the classification of each edge.