Coming events:
   Monday -- review session.  This will include solutions to
      past written homework and sample exams.
   Wednesday -- midterm exam.
   Friday -- exam solutions (unless some are late), maybe
      some algorithmic software demo (fun).

In the current directory, see review.txt for some weekend review
advice, and also there is an old exam (mid-2009.pdf).  The Monday
review session will go better if you prepare, don't you think?

Today, finishing 4.2, two more Digraph algorithms.

  * The Kosaraju-Sharir SCC algorithm (two passes of DFS, linear time).
    First pass: let G'=reverse(G), and do a full DFS traversal of G',
      keeping track of their post order (finishing order).
    Second pass: Do a DFS traversal of G, considering the vertices
      in the reverse of the post order from the first pass.
    Claim: each tree in the secon pass spans a SCC!

  * Transitive closure, O(V^2) space and O(VE) time:
    just a DFS from each vertex.
    Sometimes faster (not in book?):
      first compute and "contract" the SCC's, then do above.

Slides:
  continuing at page 46 (skip examples of cycle detection)
Movie:
  42DemoKosarajuSharir.mov