📄 workshop3.html
字号:
<html><head>
<title>Data Structures and Algorithms - Workshop 2</title>
</head>
<body BGCOLOR="#ffffff">
<H1>Data Structures and Algorithms</H1>
<HR>
<H2>Workshop 3 - Minimum Spanning Trees</H2>
For the assignments which follow from this workshop,
you are expected to produce a program which
reads a description of a problem from a file,
calculates the minimum spanning tree
and prints out the tree and its cost.
<H4>Rules</H4>
<OL>
<LI>Nodes are labelled with an arbitrary string.
In the present problem, this string will not be longer than
100 characters.
<I> However, it would be a mistake to submit a program in which
you cannot trivially change this requirement!</I>
<LI>Node labels have no spaces in them.
<LI>For simplicity, edges have the same cost in both
directions,
<I>ie</I> the cost of edge "abc"->"pqr" is the same as that for
"pqr"->"abc". <I>A program which can be trivially extended
to handle asymmetric costs will attract a small bonus.
You should indicate in your report the changes that are necessary.</I>
<LI>All edge costs are positive.
<LI>Unspecified edges are assumed to be impossible.
(Your program should use a suitable representation!)
<LI>You may print out the resulting MST in any intelligible
format, but your report should obviously explain the format.
</OL>
<H4>Procedure</H4>
<OL>
<LI>Find a partner and decide how to split
the work for this assignment between yourself and your
colleague.
<P><LI>In the tutorial session preceding the lab session,
start the design of the ADTs that you will need for this assignment.
<FONT COLOR=red><I>By now, you should interpret "design" as meaning "design and
formally specify".</I></FONT>
<P><LI>Get the full design checked off by the lecturer or tutor
before proceeding to implement your solution.
<P>
Note that, for graphs, there are a number of ways of implementing
the graph structure.
You should understand by now that the specification and the implementation
details are quite separate.
You can derive a specification by looking at the requirements of the
problem which specify abstract operations that will be needed.
<P><LI>For assignment 3,
<OL TYPE="a">
<LI>Formally test <I>each</I> ADT used
by performing an equivalence class analysis on it
and generating a program (or programs) to check each class.
<P>
Note that while you may have constructed the full MST program
at this point, it is not required for this submission.
</OL>
<A NAME="w4">
<P><LI><FONT COLOR=red>For assignment 4,</FONT>
<OL>
<LI>Submit a program which will read the test file and
find and print out the MST.
<LI>Design (or automatically generate) additional test sets
to formally test the whole program.
<LI>Confirm that the running time of the whole
algorithm is as expected.<BR>
Running time of the algorithm <B>does not</B> include the
time to load the data from the test file.
</OL>
<P>For 2 and 3,
you may generate the test data within the test programs themselves,
<I>ie</I> it is not necessary to read data from a file.
A script which automatically runs the test program with
a set of test files is also acceptable.
<P><LI>
<FONT COLOR=red>Submissions</FONT>
<OL TYPE="a">
<LI>Both submissions should be accompanied by an
appropriate report.
<LI>You should make one submission with your partner.
Either one of you can make the actual submission:
just make sure that you have collected <I>all</I> the relevant
files into the submission directory.
<LI>Your report (and the program file prologues) should clearly
identify the contributions of each partner to the joint submission.
</OL></OL>
<H4>File format</H4>
<CENTER>
<TABLE BORDER=2>
<TH COLSPAN=2>Lines</TH><TH ROWSPAN=2>Content</TH><TH ROWSPAN=2>Format</TH>
<TH ROWSPAN=2>Notes</TH></TR>
<TH>From</TH><TH>To</TH>
<TR><TD>1</TD><TD>1</TD><TD><B>n</B></TD><TD>%d</TD><TD>Number of nodes</TD></TR>
<TR><TD>2</TD><TD><B>n</B>+1</TD><TD><B>label<SUB>i</SUB></B></TD>
<TD>%s</TD><TD>Node Label</TD></TR>
<TR><TD><B>n</B>+2</TD><TD><I>EOF</B></TD>
<TD><B>label<SUB>i</SUB> label<SUB>j</SUB> c<SUB>ij</SUB></B></TD><TD>%s %s %g</TD><TD>Edge descriptor and weight</TD></TR>
</TABLE></CENTER>
<P>Notes:
<UL>
<LI>Fields are separated by spaces.
<LI>The remainder of a line is to be ignored and may be used for comments.
<LI>Costs are real numbers: you may assume costs are less than 10<SUP>6</SUP>.
</UL>
<P>
A sample of the format may be found in
<A HREF="mst.test" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/source/mst.test" TARGET="Test file">mst.test</A>.
<H4>Submission</H4>
Follow the same
<A HREF="submit.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Labs/submit.html">submission procedure</A>
used for the previous assignments.
<H4>Dates</H4>
<CENTER>
<TABLE HSPACE="80%" BORDER=1>
<TR>
<TD>Designs Checked and<BR>
Signed Off</TD><TD>5pm, Thu 19th Sept<BR>
Designs submitted by this deadline will be
checked<BR> and returned by the following day.</TD></TR>
<TR><TD>Assignment 3<BR>ADTs programmed and verified</TD>
<TD>5pm, Tue 8th Oct</TD></TR>
<TR><TD>Assignment 4<BR>Full program verified<BR>
Time complexity verified</TD><TD>5pm, Thu 24th Oct</TD></TR>
</TABLE>
</CENTER>
<P>
Proceeding to the coding stage <i>without</i> having your design
checked is not likely to be productive.
For a quick review and sign-off, you may bring your design
to me any time before the deadline:
otherwise, submit it using the normal submission procedure as
the "3des" assignment.
The submission procedure automatically sends me an email message
when you have submitted - I will attempt to review all designs
within 24 hours and will email you my comments.
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -