- provide them with an implementation of either the radix sort or
the red-black tree for them to test,
*and* - get an implementation of the other algorithm for testing yourself.

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.

- quicksort (use the standard library function
`qsort`unless you think that you can do better!) - radix sort

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,

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!

Table of Contents

© John Morris, 1996