Reading

These notes.

Quiz questions

Do your problem sets!

Project 1

Discussion on how to follow directions! Program results. Surprise: fastest program was in Java.

Loops and directed acyclic graphs (DAGs)

Review quiz problem P6, where DFSVisit finds a cycle. Remember: there is a cycle in a directed graph G if and only if DFSVisit finds a vertex v in the inner loop that is colored gray. Note: we really need to call DFSVisit repeatedly (though always on an undiscovered vertex (i.e. colored white), so that we look at all parts of the graph. This is the "DFS" from the previous notes. Specifically, we will end up looking at every edge exactly once. This means we can determine whether there is a cycle (and find one if it exists) in time $O(n + e)$, where $n$ is the number of vertices and $e$ is the number of edges.

A Directed Acyclic Graph is called a "DAG", and these graphs have lots of important applications in computer science. We looked at two important ones

  1. Makefiles
  2. Compiler optimization. I covered an example in class from DAG-Based Optimization of IR Code in a Basic Block by Harry H. Porter

Topological sort, and reviewing the quiz problems

Reviewed quiz problem 5. What we discovered is this:

Theorem: Given graph $G$, if a full depth-first search of $G$ is performed, and the vertices of $G$ are ordered in the reverse of the order in which they are colored black during the search (i.e. $u$ comes before $v$ only if $u$ was colored black later than $v$), then all edges in the graph aer oriented from vertices earlier in the order to vertices later in the order.

An ordering like this is called a "topological sort" of the graph. Of course, this is only possible for DAGs. We talked about the importance of topological sort in producing schedules for tasks with ordering constraints defined by a DAG.