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.
Testing means both 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.
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.
For the radix sort, you will find it helpful to build some simple
classes to manage bins, etc.
Think about how to structure a solution to the problem
before diving in to write code!
You may, of course, use any suitable radix for sorting ..
base 16, base 32, base 69, etc, 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.)
Since the qsort function asks you to supply the compar
function, you should use the same approach to defining your
radix sort function, ie you should also pass it a
compar 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
(ie 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.
If you time the performance of these two for different values
of n,
then you should expect to find some interesting results!
The most interesting results will come for very large n.
You should know what to expect for small n.
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!
Submit both assignments using the submission procedure as before.
Hopefully it will be working without error messages before
you need it again!
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.
The testing of this class should include measurement of the
black height 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.
Basically you should use the same submission procedure as before.
However note that there are now four assignment labels:
radix_i, radix_t, rb_i and rb_t.
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, etc,
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.
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!
If you want the feedback to get back to both
partners, make sure to include both email addresses in the report!
Workshop 3
Sorting Algorithms
Build programs to sort arrays of 32-bit integers using:
Workshop 4 - Red-Black Trees
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.
Submission
For full marks, each member of the class should be responsible
for one implementation and 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.
Due Date
Monday, October 20, 5pm
Table of Contents
© John Morris, 1996