EL9343 Homework 5HW5 SolutionCS-UY MISC

EL9343 Homework 5 (Due May 3 rd, 2020) This Assignment is longer than before, start early. No late assignments accepted All problem/exercise numbers are for the third edition of CLRS text book 1. Show the ordering of vertices produced by TOPOLOGICAL-SORT when it is run on the DAG below. Assume that for loop of lines 5—7 of the DFS procedure (page 604 in CLRS) considers the vertices in alphabetical order, and assume the adjacency list is ordered alphabetically. Solution: This is the graph after we run DFS on the graph: The left number is the discover time and the right number is the finish time. According to the TOPOLOGICAL-SORT(G), we can get the ordering of the vertices should be: p, n, o, s, m, r, y, v, x, w, z, u, q, t. 2 2. Run the procedure STRONGLY-CONNECTED-COMPONENTS on the graph below. Show the: (a) The finishing times for each node after running DFS in line 1 (b) The DFS forest produced by line 3 (c) The nodes of each tree in the DFS forest produced in line 3 as a separate strongly connected component. Assume that for loop of lines 5—7 of the DFS procedure (page 604 in CLRS) considers the vertices in alphabetical order, and assume the adjacency list is ordered alphabetically. Solution: (a) As shown below, the discover time and finish time lie on two sides of each node, the left is the discover time, the right is the finish time. (b) The result of DFS on