CS 170 Reading Quiz -- Week 5, Monday

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

1. The BFS algorithm shown in class only inserts a vertex v into the queue if (a) the vertex has not been visited before, and (b) the vertex is not already in the queue. Suppose that we remove these restrictions. Would the modified algorithm still visit every node that is reachable from the starting point?

In other words, the modified algorithm is as follows:

Modified-BFS(G,s):
1. Mark s.
2. Create an empty list Q, and insert s into Q.
3. While Q is not empty:
4.  Remove the node from the front of Q; call it u.
5.  for each edge (u,v) in E:
6.    Append v to the end of the list Q (whether or not v is already marked,
      and whether or not v is already in Q).
7.    Mark v.

Notice that when running Modified-BFS, a vertex might appear multiple times in the list Q.

Are we guaranteed that Modified-BFS(G,s) will eventually visit every node that is reachable from s? Explain briefly.

2. Suppose we run Modified-BFS(G,s), where G is a dag (i.e., G has no cycles) and s is some vertex in G. Is its worst-case running time guaranteed to be O(|V|+|E|), in this case?

If you say "yes", explain why briefly. If you say "no", explain why briefly; how bad could the asymptotic running time be, as a function of |V|, a function of |E|, or a function of both |V| and |E|?

Clarification added 2/22: If you say "no", it's fine to give a rough lower bound for the worst-case asymptotic running time as a function of |V|, or as a function of |E|, or as a function of both |V| and |E| (your choice). Don't spend too long on this. (You don't have to give a complete characterization of the worst-case running time when running Modified-BFS(G,s) on dags with exactly n vertices and exactly m edges, for every n,m.)

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