Differences

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

Link to this comparison view

cs-312:hw12 [2014/12/31 23:00] (current)
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
  
cs-312/hw12.txt ยท Last modified: 2014/12/31 23:00 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0