CS 170 Reading Quiz -- Week 3

Please fill out this quiz, and press the "Submit" button at the end. Don't collaborate with anyone on quiz exercise solutions.

Please answer all questions.

Name:

SID: [No spaces and no dashes.]

Login ID : [e.g., cs170-xy]

1. In a DAG, when performing depth-first search, is it always the case that the first vertex to be popped from the stack is necessarily a sink (a vertex with no outgoing edges)?

Begin your answer with a "yes" or a "no", and then give a brief justification if yes; otherwise give a small counterexample.

2. Let G be an undirected graph. Suppose we do depth-first search starting from some vertex and we record the pre and post numbers. Is it possible to have an edge {u,v} where pre(u) < pre(v) < post(u) < post(v)?

Begin your answer with a "yes" or a "no", and then justify youro answer. One sentence of explanation is enough.

3. What did you find difficult or confusing about the reading or the lectures, and what would you most like to see explained better? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.

CS 170 home page