Section 3.5 This section discussed the concept of connectivity in directed graphs. Directed graphs are distinct from undirected graphs because instead of a node having a list of connected nodes, each node has two lists – one with nodes to which it has edges and one with nodes from which it has edges. We can traverse a directed graph using BFS or DFS, similar to the way we use them to search undirected graphs with the same running time: O(m+n). The main thing to remember is that these searches are only returning paths in one direction, for instance, the path from s to t, but not necessarily the paths from t to s, which might not exist. A graph is strongly connected if for every two nodes there is a path from u to v and a path from v to u, which also means the two points are mutually reachable (Proof p. 98). From the proof in the book, we arrive at a strong component, which contains a node s in a directed graph to be the set of all v such that s and v are mutually reachable (p.99). We can find the strong component by running BFS twice, in reverse on the second round. I would give this section a 10—the concept of connectivity in directed graphs was explained pretty logically and I feel good about my understanding of it. The slides with visuals from class also reinforced my understanding. Section 3.6 This section reviewed directed acyclic graphs and topological ordering. A directed acyclic graph is any directed graph that contains no cycles. We can use DAGs to represent precedence relations or dependencies – anything with a hierarchical ordering, I think. A topological ordering is “an ordering of [graph G’s] nodes as v1, v2, …, vn so that for every edge (vi, vj) we have i