Homework 9
Document last modified: 

  1. (6) Show the data structure p 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 5 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, x4)
      4. UNION(x4, x5)
      5. FIND-SET(x6)
      FIND-SET ( x )

         if p[ x ] ¹ x then p[ x ] ¬ FIND-SET( p[ x ] )
         return p[ x ]
      UNION (x, y)

      a ¬ FIND-SET (x)
      b ¬ FIND-SET (y)
      p[b] ¬ a                    

     

  2. (4) Given an adjacency-matrix representation of a directed graph as on page 528, what is the time to compute the out-degree of any one vertex? _________

    The out-degree of every vertex? __________

    What is the time to compute the in-degree of any one vertex? _____________

    What is the time to compute the in-degree of every vertex? ______________

     

  3. (4) Given an adjacency-list representation of a directed graph as on page 528, what is the time to compute the out-degree of any one vertex?

    ___________________________________________________________

    The out-degree of every vertex? _____________________

    What is the time to compute the in-degree of any one vertex? ________________

    What is the time to compute the in-degree of every vertex? _____________________

     

  4. (2) Using Figure 22.3 as an example, show that the breadth-first tree computed by BFS can depend on the ordering within the adjacency list.

     

     

  5. (2) Give a counter-example to the conjecture that if there is a path from u to v in a directed graph G, and if d[u]<d[v] in a DFS of G, then v is a descendant of u in the depth-first forest produced.








     
  6. (3) Show the ordering of vertices produced by TOPOLOGICAL-SORT when it is run on the DAG of Figure 22.8. 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.









     
  7. (2) Show how the procedure STRONGLY-CONNECTED-COMPONENTS works on the graph below. Specifically, give the forest produced in line 3 and the graph GSCC. Shade vertices that are roots of each depth-first tree produced by the DFS on GT.

    G a b c d e f g h i j
    d 1 2 3 6 7 10 13 14 15 17
    f 12 5 4 9 8 11 20 19 16 18
    p NIL a b a d a NIL g h h

 

Turn in

  1. Cover sheet with your name, C455, date, and Homework 9.
  2. Typed or very neatly handwritten answers.