Design and implement an algorithm for finding the ``Euclidean'' minimum spanning tree of a large random set of N points in the plane. This is the minimum spanning tree of the graph consisting of the given points and the N(N-1)/2 edges connecting all pairs of points, with edge weights defined to be the distance between the two points. Assume that the point coordinates are random numbers between 0 and 1, but don't bother to use more than 20-bit precision.
The main point of this assignment is the observation that the vast majority of the edges (the long ones) in the definition above actually never need to be constructed. The input to the algorithm is N points and the output is N-1 edges, and for random point sets it is extremely unlikely that all N(N-1)/2 edges are needed. Indeed, there is no requirement to actually build any graph, though it might be convenient to do so for many methods. The problem can be shown to be sufficiently well related to sorting that time proportional to N logN should be required. You should use some variant of Prim's algorithm that lets avoid looking at most of the N(N-1)/2 edges.
For a change of pace, evaluate how fast your program is by seeing how large a tree it can compute in a fixed amount of time. Turn in your documented source code and runs that take 1 second, 2 seconds, and 10 seconds. Show the number N of points and the total length of the edges in the tree computed. How big do you think this length is, as a function of N? Also turn in a drawing of a 1000-node tree.
Advice: You don't need to compute square roots.
Due: 11:59PM Thursday, April 20.