Do Problem 6 from
Lecture 17, i.e.
A vertex is a "source" if there are no edges coming into it
from other vertices. Design an algorithm that takes a graph G
and determines all sources in the
graph. Analyze your algorithm in both representations assuming
that G has n vertices and e edges.
P2
Consider the algorithm findCommon from
Lecture 17 (repeated
below). Andconsider it run on the graph G (n=10) shown below
and input L=[7,5,9] (k=3).
Show the contents of the queue Q and map M (which you can show
as a list of key-value pairs) at the beginning of each iteration
of the while loop up until the algorithm returns. (You should
"return" on the 6th iteration.)
P3
Consider the generic search algorithm from the class notes for
class 18. Prove that the
following is an invariant for the while loop:
\[
\text{if $i$ is the number of completed iterations, then }
n - i = \text{# unvisited nodes} + \text{# nodes in store $S$}
\]
and use this result to give a worst-case analysis of the running
time of breadth-first search in graph $G$ with initial vertex $s$
where $G$ has $n$ vertices and $e$ edges, and there are $r_s$
vertices in $G$ that are reachable from $s$. Assume the
adjacency list representation. A big-O upper bound analysis is sufficient.
P4
Consider the findCommon algorithm from Problem 2.
Note that this is nothing more than breadth-first search, except
that we start not from a single node but from the k nodes in L.
Analyze the worst case running time of the algorithm, assuming
the adjacency list representation, in terms of
$n$, the number of nodes in $G$, and $e$, the number of edges in
$G$. A big-O upper bound analysis is sufficient.
Question: does using a balanaced binary tree seem like a good
choice? What if you knew you'd find a common descendent
relatively near the vertices in $L$?
P5
Consider the graph shown to the right.
Follow the DFSVisit algorithm given
in Class 19 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
P6
In the same graph as above, add the edge 4→5. Then
start DFSVisit at vertex 10 and show the state of the stack when
the algorithm first discover's a cycle.
