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 generic search algorithm from the
class notes. 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.
Problem 1 (assessment: self_______ final_______)
Suppose we implement our generic search algorithm with a
balanced binary tree to keep track of the "visited" vertices.
I.e. when a vertex is visited we put it in the tree, and when we
look at a child v, we check the tree to see if it's been
visited. Analyze the worst-case running time of search done
this way in terms of $n$ and $e$. Note: assume the add and
remove operations on store $S$ take constant time.
Problem 2 (assessment: self_______ final_______)
Analyze the same scenario as before, but do your analysis in
terms of $n$, $e$ and $R_s$, where $R_s$ is the number of
vertices that are reachable from $s$. [Imagine a situation
where a graph as billions of nodes and trillions of edges, but
there are only hundreds of vertices reachable from $s$.]