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 1 (assessment: self_______ final_______)
Consider the minimum spanning tree below.
(The heavy edges are the spanning tree.)
In our proof of correctness, we described how if
$T'$ is the "current" tree for Prim's algorithm at a particular
point, then the greedy choice of a minimum weight edge from a
vertex in $T'$ to a vertex not in $T'$ is part of some minimum
spanning tree.
Suppose we were running Prim's algorithm extending $T'$ and we
chose $(u,v) = (5,7)$. The minimum weight spanning tree in
the picture extends $T'$ but doesn't include $(u,v)$. Show
how the proof from class/notes would modify the minimum
spanning tree in the image to get a minimum spanning tree that
includes $(u,v)$. Be sure to label the vertex $y$ and $z$
referenced in the proof.
