CS211 S07   Quiz 3   4/12/07

Please write legibly.

1. My name is_______________________________________________________________________

2. My Cornell NetId is_____________________

3. Consider the directed graph specified by the following
adjacency matrix.  There is an edge from s to t iff the 
entry in the s-th row and t-th column is 1.

    a b c d
   _________
a | 0 0 0 0
b | 1 0 1 1
c | 1 0 0 0
d | 1 0 1 0

(i) What is the outdegree of vertex a? ____

(ii) What is the indegree of vertex a? ____

(iii) Is the graph acyclic? yes___  no___

(iv) Write down a simple path of length 3. ____________________________________________

(v) Write down a topological sort of the graph. _______________________________________