I would like to go over solutions to the midterm exam, however there
is one late makeup this afternoon, so I cannot do it.   I'll have to
send out solutions by email instead.

Our next topic, after break, will be Section 4.3, on Minimum Spanning
Tree (MST) algorithms.  They solve the following problem:

    Given an graph with edge weights, find a tree that spans
    all the vertices, and so its total edge weight is minimum.

It turns out that there are efficient solutions to this problem,
because a simple greedy approach actually finds the best solution.
"Greed is good".

But I don't expect enough attendance to start that in earnest today,
so instead I'll go "off the rails" today, and talk about a related
problem that I've studied, the "traveling salesman problem" (or TSP).

At first blush, TSP sounds a lot like MST:

    Given a graph with edge weights, find a closed tour that spans
    all the vertices, and so its total edge weight is minimum.

(Note: the tour is allowed to visit a vertex more than once.)

Unlike MST, this turns out to be a very hard problem, at least if we
want to solve it exactly.  (It is NP-complete.)  "Greed" does not work
so well here!

Since this is a hard problem, we consider fast algorithms finding an
"approximate" solution instead, i.e. tours with total weight at most
some constant times the best possible weight.

We'll see given an MST (which we'll see how to compute in Section
4.3), we can use that to get a 2-approximate tour.  With a little more
work (Christofides algorithm), we can get that down to a 3/2
approximate solution.   But that is about as far as we know how to go!

This topic is outside our textbook, but see:
  http://en.wikipedia.org/wiki/Christofides_algorithm
  http://en.wikipedia.org/wiki/Travelling_salesman_problem (metric TSP)

I'm thinking TSP approximation will be the hw4 program topic.
But don't worry about that until after break!