📄 w3_1997.html
字号:
<html><head>
<title>Data Structures and Algorithms - Workshop 3</title>
</head>
<BODY BGCOLOR="#ffffff">
<H1>Data Structures and Algorithms</H1>
<HR>
<H2>Workshop 3 & 4</H2>
These two assignments should be undertaken as a collaborative effort.
You are expected to write the <I>implementation</I> of one assignment
and the <I>test program </I> for the other.
Thus you should pair up with another member of the class and
<OL TYPE=a>
<LI>provide them with an implementation of either the radix sort or
the red-black tree for them to test, <I>and</I>
<LI>get an implementation of the other algorithm for testing yourself.
</OL>
Thus you are expected to design and code <I>one</I> algorithm and
<I>one</I> extensive test of an algorithm written by someone else.
<P>
Joint submissions by your team will be preferred, but in cases of
difficulty (your team-mate wins the lottery and, naturally, decides
that there are more fun things in life than red-black trees),
you should make sure that you submit one algorithm implementation
and one testing program.
For your testing program, you can obtain an implementation from any
other member of the class if necessary.
<P>
<B>Testing</B> means <B>both</B> verifying that the algorithm is
correct (so perform an equivalence class analysis of the input to
make sure that you covered all the tests) and verifying that its
time complexity is as expected.
<P>
The person performing the testing will generally be expected to be
responsible for the bulk of the submission report.
However the implementor may, of course, contribute any (short)
notes to the report.
<A NAME=workshop3>
<H2>Workshop 3</H2>
<H3>Sorting Algorithms</H3>
Build programs to sort arrays of 32-bit integers using:
<OL>
<LI>quicksort (use the standard library function <TT>qsort</TT>
unless you think that you can do better!)
<LI>radix sort
</OL>
<P>
For the radix sort, you will find it helpful to build some simple
classes to manage bins, <I>etc</I>.
Think about how to structure a solution to the problem
<B><I>before</I></B> diving in to write code!
You may, of course, use any suitable radix for sorting ..
base 16, base 32, base 69, <I>etc</I>, should all work
reasonably well.
(You may be able to think of reasons why certain bases will
perform better than others - see below for some hints.)
<P>
Since the <TT>qsort</TT> function asks you to supply the <TT>compar</TT>
function, you should use the same approach to defining your
radix sort function, <I>ie</I> you should also pass it a
<TT>compar</TT> function and the size of the elements that
are being sorted. This is partly to ensure that you eliminate
some systematic variation from your timing experiments
(<I>ie</I> you time both functions under as nearly the same
ground rules as possible),
but also to give you some practice in writing a function to
use as a data type.
<P>
If you time the performance of these two for different values
of <B>n</B>,
then you should expect to find some interesting results!
The most interesting results will come for very large <B>n</B>.
You should know what to expect for small <B>n</B>.
<P>
Write a report that interprets your results.
Some of the phenomena that you observe will be related to the
way that the operating system treats virtual memory and
aspects of the MIPS architecture of the processors.
You might find some useful insights if you interpret your data
in terms of factors that you may have learnt in other second
year courses!
<P>
Submit both assignments using the submission procedure as before.
Hopefully it will be working <B>without</B> error messages before
you need it again!
<P>
<A NAME=workshop4>
<H2>Workshop 4 - Red-Black Trees</H2>
Your problem scenario is a situation where you have to maintain a
searchable collections of items. The items in the collections are
always changing - in fact you have, on average, one new item and
one deletion for every 10 searches.
<P>
Write a general purpose class that puts items into a balanced
tree - use the red-black tree algorithm, unless you are absolutely
convinced that you can get better performance from an AVL-tree or any
other dynamically balanced tree.
<P>
The testing of this class should include measurement of the
<B>black height</B> of the tree as randomly valued key items
are added. It should also time searches and additions to
measure the time complexity of the add and find operations.
These should confirm the theoretical expectations.
<P>
<HR>
<H3>Submission</H3>
For full marks, each member of the class should be responsible
for one implementation <I>and</I> one test exercise.
Assignments are compulsory and failure to submit one is the
same as failing the course.
Thus a late assignment may not get you any marks, but it will
allow you to sit the exam.
<P>
Basically you should use the same submission procedure as before.
However note that there are now <I>four</I> assignment labels:
radix_i, radix_t, rb_i and rb_t.
<P>
If you and your team-mate have a complete submission (implementation,
test and report), submit it under the ?_t label ("t" = testing).
If you are submitting an implementation by yourself because
of some administrative problem (your testing partner won the lottery),
submit it under the ?_i label ("i" = implementation):
this should hopefully be the rarer case - and if you are able to
arrange a last minute test, you can submit the tested code,
report, <I>etc</I>,
under the ?_t label. I will look at ?_t submissions first,
so if there is something there from you, I will assume it
supercedes anything I might find elsewhere.
<P>
<FONT COLOR=green>Of course, all this depends on getting the
system problems sorted out - look in this space for new instructions
if the old ones won't work!</FONT>
<P>
<FONT COLOR=red>If you want the feedback to get back to <B>both</B>
partners, make sure to include both email addresses in the report!
</FONT>
<H3>Due Date</H3>
Monday, October 20, 5pm
<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>
© <A HREF=mailto:morris@ee.uwa.edu.au>John Morris</A>, 1996
</SMALL>
</BODY>
</HTML>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -