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 proved that if
$T'$ is the "current" tree for Prim's algorithm at a particular
point, then the greedy choice of a minimum weight edge $(u,v)$ from a
vertex $u$ in $T'$ to vertex $v$ not in $T'$ is part of some minimum
spanning tree. We did that by showing how to take a minium
spanning tree $T^*$ that extends $T'$ but doesn't include
$(u,v)$ and transform it into a minimum spanning treee that does
include the edge $(u,v)$
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
does include $(u,v)$. Be sure to label the vertices $y$ and $z$
referenced in the proof.
