Advanced Data Structures

Complexity of a Minimum Weight Spanning Tree Algorithm

• Write a MWST application that performs experiments with the RoundRobin algorithm. Each run of the algorithm accepts on input a representation of an edge-weighted graph with n vertices and m edges (in the format "n m CR (x y w CR)^m" of m+1 lines of text, where x and y are integers 1< x=/=y< n are vertex identifiers and w is the integer weight of the edge (x,y)) and returns its minimum weight spanning tree.

• Your algorithm should include two implementations for each of the ADT Partition and MergeablePriorityQueue, one as in the RoundRobin algorithm in the text (ie., DisjointSets and LeftistHeap, respectively) and one other of your choice.

• Investigate time complexity of your implementations by performing and graphing the relative timing of computations (not the I/O) in the four cases for graphs with n=100..10,000 and m=n loglog n.

• The recommended social configuration: three teams of three persons each plus a two person team for providing a uniform input data generator. In each team, one person will be responsible for LeftistHeap and a Partition development, another for a MergeablePriorityQueue and DisjointSets, and one for the driver, stubs, coordination and delivery. The two-person team should test their data by programming and running the text-based Round Robin algorithm.

  And the teams are (the envelope, please!)

  1. James, Jim and DongKi
  2. Colin, Jimmy and Ryan
  3. Peter, Paul and Kerry
  4. Dave and Brandon