##### Differences

This shows you the differences between two versions of the page.

 — cs-312:hw12 [2014/12/31 16:00] (current)ringger created 2014/12/31 16:00 ringger created 2014/12/31 16:00 ringger created Line 1: Line 1: + = Homework Assignment #12 = + + == Objectives == + To solve problems using the strongly connected components algorithm. + + == Exercises == + + Show all work.  i.e., justify your answers. + + ===Question 1=== + Problem 3.4 graph (i) in the textbook. ​ Just apply the SCC-finding algorithm to identify the SCCs.  Start at A, and be sure to show your process and to give your answer clearly as sets of vertices. ​  You do not need to do parts (a)-(d). + + ===Question 2=== + Problem 3.4 graph (ii), parts (a)-(d). ​ Re-run the SCC-finding algorithm on this graph, but this time start step 1 of the SCC algorithm at vertex G in order to compute the post-order numbers. + * (Note: we already ran the algorithm on this graph in class, but that time we started at vertex A.  For this problem, we're trying a different starting point, to find out whether the starting point actually matters.) + + ===Question 3=== + 3.15 in the textbook