Workshop 3
Sorting Algorithms
Build programs to sort arrays of 32-bit integers using:- 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, 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 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
©
, 1996