Name: ____________________________________________________ Alpha: _____________________
Describe help received: _________________________________________________________________
Per-problem assessment:
• 5 (Perfect): Correct solution
• 4 (Good effort): Good effort, solution may or may not be correct.
• 2 (Poor effort): Some basic misunderstandings demonstrated that could have
been cleared up by reading the notes or giving a serious try.
• 0 (No effort): No progress towards a solution.
Problem 0 (assessment: self_______ final_______)
Consider the graph shown to the right.
Follow the DFSVisit algorithm from the
in
class notes using vertex 2 as
your starting point. Keep track of "parent" and "color", and write
down the order in which the vertices are colored black. Draw
the graph with all vertices laid out in a single line across the page,
in the reverse of the order in which they were colored black, and then
draw all the edges. What do you notice about the edges?
Note: in the underlying adjacency list, assume nieghbors are listed in
sorted order (increasing), so that for example the neighbors of vertex
two would be listed like this:
2 → 4,5,9