📄 feedback4.html

📁 Data Structure Ebook
💻 HTML
字号:
<HTML><HEAD>
<TITLE>Data Structures and Algorithms - Assignment 4</TITLE>
</HEAD>
<BODY BGCOLOR="#ffffff">
<H1>Data Structures and Algorithms</H1>
<HR>

<CENTER><H3><FONT COLOR=red>
Feedback from assignment 4
</FONT></H3></CENTER>

<OL>
<LI><H4>Testing the MST</H4>
Proving your MST algorithm has two parts:
<UL>
<LI> Proving that a spanning tree is produced <I>and</I>
<LI> Proving that it's the <B>minimum</B> spanning tree.
</UL>
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, <I>etc</I>) on which the MST algorithm relies
are performing correctly <BR>
<CENTER><I>or</I></CENTER>
you could do something like exhaustively generate <B>all</B>
the possible trees and thus demonstrate that indeed the
tree produced by your program was a MST.
<P>For maximum marks, you were expected to <I>address</I>
both parts of the problem in your report and do something
about the first part.
<P>
One of the post-conditions of your <TT>MST</TT> method should have
been:
<BLOCKQUOTE>
The tree produced is a spanning tree.
</BLOCKQUOTE>
Adding an additional method <TT>SpanningTree( Graph g )</TT>
to your graph class and using it as the post-condition for
<TT>MST</TT> is the best approach.
<P>
You can then simply run the <TT>MST</TT> 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!
<LI><H4>Complexity of MST</H4>
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.

<P>
<HR>
<A HREF="ds_ToC.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/ds_ToC.html">Table of Contents</A>
<HR>
<SMALL>
&copy; <A HREF=mailto:morris@ee.uwa.edu.au>John Morris</A>, 1996
</SMALL>
</BODY>
</HTML>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -