CSE310 HW04 Grading KeysPlease note that you have to typeset your assignment using either LATEX or MicrosoftWord. Hand-written assignment will not be graded. You need to submit a hardcopybefore the lecture on the due date. You also need to submit an electronic version viathe white board. For the electronic version, you should name your file using the formatCSE310-HW04-LastName-FirstName.1. (20 pts) As we learned in class, Kruskal’s algorithm for computing a minimum spanning tree(MST) uses a disjoint-set data structure to keep information about the nodes that belong toeach tree in the spanning forest it maintains. Suppose we run Kruskal’s algorithm on thegraph G(V, E) of the figure below, with edge weights w(u, v) as indicated. Suppose that weuse union-by-rank and find-with-path-compression when performing the disjoint-set operations.Also assume that we represent each undirected edge in alphabetical order of itsend-vertices. For example, the edge connecting nodes 5 and 3 is denoted as (3, 5),not (5, 3).1 2 34 5 611121314151617181920Figure 1: Graph for P1.(2 pts) Show the resulting disjoint-set data structure (in array notation) after we perform allMake-set(i) operations. You should write your answer using the following format.i 1 2 3 4 5 6A[i] 0 0 0 0 0 0Grading: Binary.(18 pts) Show the resulting disjoint-set data structure (in array notation) at theend of each iteration of the “for each edge (u, v) in E in non-decreasing or-der of weights do” loop. You should write your answer using the followingformat.1i 1 2 3 4 5 6After Iteration 1 A[i] 2 -1 0 0 0 0After Iteration 2 A[i] 2 -1 0 2 0 0After Iteration 3 A[i] 2 -1 0 2 0 0After Iteration 4 A[i] 2 -1 2 2 0 0After Iteration 5 A[i] 2 -1 2 2 2 0After Iteration 6 A[i] 2 -1 2 2 2 0After Iteration 7 A[i] 2 -1 2 2 2 0After Iteration 8 A[i] 2 -1 2 2 2 2After Iteration 9 A[i] 2 -1 2 2 2 2Grading: 2 pts for each iteration.(5 pts) For the graph in Fig. 1, perform breadth first search from vertex 1. You shouldassume that the edge adjacency lists are in alphabetical order. Draw the BFStree, with the vertices at the following relative positions.1 2 34 5 6Grading: Binary.(5 pts) For the graph in Fig. 1, perform depth first search from vertex 1. You shouldassume that the edge adjacency lists are in alphabetical order. Draw the DFStree, with the vertices at the following relative positions.Grading: Binary.21 2 34 5 6(20 pts) Figure 2 shows a directed graph G. Assume that the adjacency list liststhe edges in alphabetical order.a b cd e f1/12 2/9 3/45/610/117/8Figure 2: Graph for P4.(12 pts) Apply depth first search (DFS) to graph G, and show the discovery andfinish times of each vertex. In the main-loop of DFS, check thevertices in alphabetical order. You can write the results on the graphin Figure 2.Grading: 1 pt for each number.(2 pts) Draw the transpose graph GTof the graph in Figure 2. The vertices aregiven for your convenience.Grading: Binary.3a b cd e f(6 pts) Apply DFS to GTto compute the strongly connected components. Youneed to show the strongly connected components and indicate the orderthey are computed.cfabdeGrading: Binary. 3 pts if only the order is
View Full Document
Unlocking...