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
- Makefiles
-
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.