Description

We will be considering complete, undirected graphs. A graph with n vertices is complete if all possible edges are present in the graph.
Consider the following types of graphs:
• Complete graphs on n vertices, where the weight of each edge is a real number chosen uniformly at random on [0,1].
• Complete graphs on n vertices, where the vertices are points chosen uniformly at random inside the unit square. (That is, the points are (x,y), with x and y each a real number chosen uniformly at random from [0,1].) The weight of an edge is just the Euclidean distance between its endpoints.
• Complete graphs on n vertices, where the vertices are points chosen uniformly at random inside the unit cube (3 dimensions) and hypercube (4 dimensions). As with the unit square case above, the weight of an edge is just the Euclidean distance between its endpoints.
For each type of graph, you must choose several values of n to test. For each value of n, you must run your code on several randomly chosen instances of the same size n, and compute the average value for your runs. Plot your values vs. n, and interpret your results by giving a simple function f(n) that describes your plot. For example, your answer might be . Try to make your answer as accurate as possible; this includes determining the constant factors as well as you can. On the other hand, please try to make sure your answer seems reasonable.
Code setup:
randmst 0 numpoints numtrials dimension
average numpoints numtrials dimension where average is the average minimum spanning tree weight over the trials.
Please pay attention to the following requirements. In order to grade appropriately, our objective is to ensure that we can run the programs without any special per-student attention. Hence we require:
• The code should run on the Harvard system (nice.fas.harvard.edu cluster of Linux machines), even if you code on another system.
• We expect an executable with the code as described above (input as described, answers should go to standard output as described).
What to hand in: Besides submitting a copy of the code you created, your group should hand in a single well organized and clearly written report describing your results. For the first part of the assignment, this report must contain the following quantitative results (for each graph type):
• A table listing the average tree size for several values of n. (A graph is insufficient, although you can have that too; we need to see the actual numbers.)
• A description of your guess for the function f(n).
Run your program for n = 16; 32; 64; 128; 256; 512; 1024; 2048; 4096; 8192; 16384, 32768, 65536, and larger values, if your program runs fast enough. (Having your code handle up to at least n = 65536 vertices is one of the assignment requirements; going up to only smaller n will hurt your score on the assignment.) Run each value of n at least five times and take the average. (Make sure you re-seed the random number generator appropriately!)
In addition, you are expected to discuss your experiments in more depth. This discussion should reflect what you have learned from this assignment; the actual issues you choose to discuss are up to you. Here are some possible suggestions for the second part:
• Which algorithm did you use, and why?
• Are the growth rates (the f(n)) surprising? Can you come up with an explanation for them?
• How long does it take your algorithm to run? Does this make sense? Do you notice things like the cache size of your computer having an effect?
• Did you have any interesting experiences with the random number generator? Do you trust it?
Your grade will be based primarily on the correctness of your program and your discussion of the experiments. Other considerations will include the size of n your program can handle. Please do a careful job of solid writing in your writeup. Length will not earn you a higher grade, but clear descriptions of what you did, why you did it, and what you learned by doing it will go far. Hints: