Data Structures and Algorithms

Feedback from assignment 4

  1. Testing the MST

    Proving your MST algorithm has two parts: The first can be done easily by inspection or by a simple program. Proving that you've found the MST is not quite so simple: you could rely on the formal proof of the algorithm and simply attempt to prove that the operations (cycle, getcheapest, etc) on which the MST algorithm relies are performing correctly
    or
    you could do something like exhaustively generate all the possible trees and thus demonstrate that indeed the tree produced by your program was a MST.

    For maximum marks, you were expected to address both parts of the problem in your report and do something about the first part.

    One of the post-conditions of your MST method should have been:

    The tree produced is a spanning tree.
    Adding an additional method SpanningTree( Graph g ) to your graph class and using it as the post-condition for MST is the best approach.

    You can then simply run the MST method on a number of carefully chosen graphs and if the post-condition assertion is never raised (except perhaps for deliberate error inputs, such as disjoint graphs which don't have a spanning tree at all!) then you can assert that your function is producing a spanning tree at least!

  2. Complexity of MST

    Incredibly, quite a number of people started their experiments with a faulty hypothesis. There is no excuse for this - the correct expression can be found in any one of a number of texts. It's also in the PLDS210 notes on the Web.

    Table of Contents
    © John Morris, 1996