Here's the practice final we went over in class today (PDF). We ran out of time in the end, but there are a couple of things I wish I had time to talk about, so I'll just blog it here (hoping it will be useful when you study for the final).
A 2-approximation for the Steiner Tree Problem. Given a graph $G = (V, E)$ and a set of terminals $T \subseteq V$, we want to find a minimum-weight subgraph $S \subseteq G$ that connects all the terminals. This problem is known to be NP-hard, so we look for an approximation algorithm. Consider the following simple algorithm:
(1) construct a metric completion $G'$ of the graph $G$ on just the vertices of $T$,
(2) compute an MST $ST$ on $G'$,
(3) return $\widehat{S} = \cup_{e \in ST} \phi(e)$ (if you want your solution to be a tree, break cycles as necessary).
The metric completion $G'$ is basically a complete graph on $|T|$ nodes, where the weight on the edge between $u$ and $v$ is the distance of the shortest path between $u$ and $v$ in the original graph $G$. The function $\phi(u, v)$ returns the set of edges on the shortest path (in fact any shortest path) connecting $u$ and $v$.
Claim: $\widehat{S}$ is a feasible solution.
By construction, it is easy to see that $\widehat{S}$ (before we break any cycle) connects all the terminal pairs. Note that breaking cycles doesn't affect connectivity.
Claim: $\widehat{S}$ is a $2$-approximation.
Let $S^*$ be an optimal Steiner tree solution. Consider an Euler's tour $ET = \langle v_1, v_2, ..., v_{2|T|} \rangle$ on $S^*$ (with each edge doubled). Note that each original edge is traversed exactly twice, so $w(ET) = 2w(S^*)$. Create a new tour $ET'$ by dropping non-terminal vertices, and vertices that showed up earlier in the tour sequence. Thus $ET'$ contains distinct vertices, and $ET'$ is a spanning tree (we don't go back to where we started because that vertex already showed up in the tour). Furthermore, the weight of $ET'$, denoted by $w(ET')$, is at most $w(ET)$ by the triangle inequality. Since $ET'$ is a spanning tree, it cannot have a lower weight than the minimum spanning tree: $w(MST) \leq w(ET')$. Combining these little pieces together, we have $w(MST) \leq w(ET') \leq w(ET) = 2w(S^*)$. Finally, we observe that $w(\widehat{S}) \leq \sum_{e \in MST} w(\phi(e)) = w(MST)$, and hence $w(\widehat{S}) \leq 2w(S^*) = 2OPT$.
