P1

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. G i 0 k 7 i->k d 1 f 6 d->f a 2 h 4 a->h c 5 a->c j 9 a->j g 3 g->h g->j h->j c->d e 8 c->e f->i e->g e->k b 10 b->g b->h b->c 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.