CS21003 Algorithms I
 CS29003 Algorithms Laboratory
Autumn 2012, L-T-P: 3-1-0 
L-T-P: 0-0-3 

Programming Assignment 9

Thanks to your programming assistance, desert-dwellers and forest-dwellers are living happily in the newly built city. The government of CSA plans to supply cooking gas connections to all the houses in the city. The gas agency plans to minimize the length of pipes while maintaining connectivity to every house. This means that we now need to solve an instance of the Euclidean minimum spanning tree problem.

The brute-force approach is to compute the distances between all pairs of houses, and run any MST algorithm on this fully connected graph. However, there are Θ(n2) edges in the graph (where n is the number of houses). This leads to Ω(n2) running time. If we look at the problem geometrically, we can arrive at O(n log n)-time algorithms. The basic observation is that if two houses are distant from one another, it is likely that the edge connecting these two houses will not be present in the MST. In other words, it suffices to look at only the neighborhood of each house, thereby restricting the connectivity graph to have only O(n) edges. One possibility is to use the Delaunay triangulation of the given points. This is, however, a topic that is outside the scope of this course. In your Algorithms II course, you would study Voronoi diagrams and Delaunay triangulation.

For the time being, you implement Rajasekaran's randomized algorithm which has an expected running time of O(n log n), assuming that the houses are uniformly randomly distributed in a square. This algorithm generates subgraphs with gradually growing neighborhood size. Such a subgraph need not be connected. However, a minimum spanning forest of the subgraph can be computed using any MST algorithm. When there is only one tree in the forest, we have obtained the desired Euclidean MST.

Write a program to do the following.

Sample output

   n = 10000000

   +++ First phase of EMST...
       No of edges in G is 35321066
       No of edges in T is 9985319
       Number of trees = 14681

   +++ Second phase of EMST...
       Largest tree is of size = 9969720
       No of edges in G is 49819152
       No of edges in T is 9999997
       Number of trees = 3

   +++ Second phase of EMST...
       Largest tree is of size = 9999998
       No of edges in G is 49819162
       No of edges in T is 9999999
       Number of trees = 1

Submission Site

Back | Home