Class Notes: Data Structures and Algorithms

Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344

Instructor: M.S. Schmalz -- TAs: TA Mailing List

Homework #5 -- Due Wed 30 June 1999 : 09.30am Revised Date

Note: Answers are in blue typeface.

• Question 1. Write pseudocode (not Java code) for the BFS algorithm we discussed in class. Beside each step, write the number of external I/O, memory I/O, incrementation, comparison, and other types of operations employed. Then, construct a work budget for each type of operation, together with a Big-Oh estimate of complexity.
  Answer: Psudeocode for BFS is given for a graph having n vertices and m edges, as follows:

  procedure:  Breadth-first-search(w)
  { initialize list L0 to contin vertex w      # 2 mem I/O
    i = 0                                      # 1 mem I/O
    while not(isEmpty(Li))  do                 # n-1 comps
    { create Li+1 = empty list                 # 1 mem I/O
      for each vertex v in Li do               # n iterations max.
      { for each edge e incident on v do       # m iter's max.
        { if e is unexplored then              # 1 comp
          { find w such that e = (v,w)         # n-1 comp's max.
            if w is unexplored then            # 1 comp
            { label e as a DISCOVERED edge     # 1 mem I/O 
              insert w into Li+1 } }           # 3 mem I/O
           else label e as a CROSS edge        # 1 mem I/O
     }}}
     i = i + 1                                 # 1 incr.
  }
  

  Each edge will be visited twice, when labelled as DISCOVERY and CROSS respectively. This entails visiting all the vertices of the graph. Thus, the minimum work will be O(n + m) comparisons. Since m = O(n²), the work is actually O(n²). The quadratic work requirement is especially noticeable in a dense graph. If an adjacency matrix representation is used, then the total work will be O(n²) in the best case, since all rows and columns will have to be examined in order to find edges incident on all vertices v.

• Question 2. Repeat Question 1 for the DFS algorithm that we discussed in class.
  Answer: Psudeocode for DFS is given for a graph having n vertices and m edges, as follows:

  procedure:  Depth-first-search(v)
  { for each edge e incident on v do          # m iter's max.
    { if e is unvisited then                  # 1 comp
      { find w such that e = (v,w)            # n-1 comp's max.
        if w is unvisited then                # 1 comp
        { label e as a DISCOVERED edge        # 1 mem I/O 
          DFS(w) }}                           # one call to DFS
      else label e as a BACK edge             # 1 mem I/O
    }
  }
  

  Each node is marked and visited at least once, and is checked for each incident edge. The time complexity of DFS is dependent on the implementation, like BFS. With an adjaceny-list representation of the graph, work can be O(n + m) comparisons, as discussed for BFS. If an adjacency matrix representation is used, then the total work will be O(n²), since all rows and columns will have to be examined in order to find edges incident on v.

• Question 3. Given the following graph specification (assume directed edges only) for G = (V,E), write out the order in which BFS visits the vertices, starting at vertex a (2 points total):
  (a) V = {a,b,c,d,e,f}, E = {(a,b), (b,c), (a,c), (c,d), (c,e), (e,f),(b,f)}.
  Answer: Assume left-to-right traversal, with repeated vertices eliminated for clarity.

  The order of traversal is a b c f e d, which can vary depending on the rotations of subtrees. For example, a b c f d e is also valid.

  (b) V = {a,b,c,d,e,f}, E = {(d,a), (b,c), (a,b), (e,b), (c,e), (b,d)}.

  Answer: One possible order of traversal is a b c d e. The comment in Question 3a) applies.

  Analyze the complexity of each case ((a) and (b), above) by constructing a work budget for each step of the traversal (2 points total).

  Answer: The number of comparisons N is the key work bottleneck in a compute-bound system, and it is proportional to the number of edges encountered at each vertex. Simply sum the degree of each vertex to find N for both a) and b).

• Question 4. Repeat Question 3 with b as the start vertex.
  Answer: (BFS) - Part a) - One possible order of traversal is b f c e d. Part b) - One possible order of traversal is b c d e a. Vertex f is unreachable. The comment in Question 3 applies to both Parts a) and b).

• Question 5. Repeat Question 3 for DFS instead of BFS.
  Answer: (DFS) Part a) - One possible order of traversal is a b f c e d. Part b) - One possible order of traversal is a b c e d. Vertex f is unreachable. The comment in Question 3 applies to both Parts a) and b).

• Question 6. Repeat Question 4 for DFS instead of BFS.
  Answer: (DFS) - Part a) - One possible order of traversal is b f c e d. Vertex a is unreachable. Part b) - One possible order of traversal is b c e d a. Vertex f is unreachable. The comment in Question 3 applies to both Parts a) and b).

Copyright © 1999 by Mark S. Schmalz.