Final Exam Reviews

Your final exam will be on Monday 05/04 from 1-4pm in WeH 7500. As usual, the exam is open-book, open-notes, etc. You should expect 6 - 8 questions, covering everything we have done in this class (but focusing on the materials after Midterm 2).

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$.

HW6 Problem 4d

While writing up the solutions to HW6, it occurred to me that Problem 4 part d might be a little ambiguous, since we never discussed approximation algorithms with randomization. For the purposes of this problem, let's allow a small failure probability: your algorithm should in polynomial time return a valid set cover with high probability (say, at least 1 - 1/n) and in expectation the cost of the solution it returns should be at most O(log n) more than the cost of the optimum solution. Once you have this it's pretty simple to get to other versions (e.g. algorithms that always return a valid set cover but only run in polynomial time in expectation), so it's fine if you end with a statement of this form (again: in polynomial time, with high probability we return a set cover and in expectation it does not cost much more than the optimum solution).

Upcoming office hours

Since this Friday is Carnival I am not planning on having office hours. I will also be out of the country all next week, and so will not be available for office hours. I'll do my best to respond to email, but it's not clear that I'll have reasonable internet access.

Midterm II

Midterm II has been graded. Some stats: Mean = 71.23, Stddev = 21.13, Median = 71. Max = 100. See histogram below for more info.

Friday office hours

I will once again be out of town this Friday, so I need to cancel my office hours. As always, feel free to email me with any questions you might have (or come to my Wednesday office hours).

Midterm II Review Session

Here are some tidbits from the review session we had in class on Friday:

Exam Format: 80 minutes, open books, notes, handouts, etc -- no laptop. 3 - 4 questions: design algorithms, write proofs, analyze running time, etc.

Topics: (everything since Midterm I).

• Graph Algorithms: Depth-first Search, Strongly Connected Components
  
  
• FFT, String Matching, String Matching using FFT, Wildcard
  
  
• Resistive Model of Graphs, Random Walks (Hitting Time, Commute
  Time, etc.)
  
  
• Linear Solvers: Direct Methods (pivoting strategy, fill, work, nested dissection), Iterative Linear Solvers.
  

Practice Midterm Solutions: We also went over the practice midterm. You can download the solutions here.

Problem 2, Homework 5

In part a) of problem 2, $C_{uv} \leq |E|$ is not achievable; you might want to prove $C_{uv} \leq 2|E|$ instead. Consequently, your upper-bound in part b) should be $2|V||E|$ (we don't mind if you show us a $4|V||E|$ bound), and hence the probability in part c) will be something like 3/4 (instead of 7/8). Thanks Yiming for pointing this out.


If you are going to use the theorem $C_{uv} = R_{uv}\times C$ (where $R_{uv}$ is the effective resistance between $u$ and $v$), keep in mind that in this case $C = \sum_{i} C_i = 2\times \sum_{e} C_e$.