I did not get the hw1 written problems graded (stayed sick!), so the
hw4 written problems are no longer required.  You can still do it as
"replacement" of a previous written homework, if you missed one, or
think you did a poor job.  I also intend to go over solutions to the
problems next week.

Today though, we'll look at the program part in share/hw4/.  Basically
I have given you a partial program, which first computes a
"goemetric graph" and an MST in that graph.   I have left two
main tasks for you:
    1. compute a TSP solution (a cyclic tour of the vertices) by
       doing a DFS of the MST.
    2. compute a second TSP solution, by applying "2-opt" moves
       to improve the first TSP.

The first is not too hard (mainly a DFS), but the second is
a bit trickier to implement well.  Finally there are also some
"extra credit" possibilities.  For more details, see hw4/Notes.txt

Remark (repeat from ../0321/Notes.txt): there are O(N lg N) algorithms
for computing the geometric MST, but they are rather tricky to
implement.  One way is to first compute the "Delaunay triangulation",
which contains the MST.  That can be done by Fortune's algorithm,
which has a nice animation here:
    http://www.diku.dk/hjemmesider/studerende/duff/Fortune/
It is in fact an "event simulation", like the particle collision system
we saw earlier, just with fancier events.

Next topic (assuming time):
 Section 4.4: shortest paths in weighted directed graphs.
 We'll just get started, hitting the slides: 44ShortestPaths.pdf
 (Even if you usually dislike the slides, see pages 25-26.)