Data Structures and Algorithms

Workshop 3 & 4

These two assignments should be undertaken as a collaborative effort. You are expected to write the implementation of one assignment and the test program for the other. Thus you should pair up with another member of the class and
1. provide them with an implementation of either the radix sort or the red-black tree for them to test, and
2. get an implementation of the other algorithm for testing yourself.
Thus you are expected to design and code one algorithm and one extensive test of an algorithm written by someone else.

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.

Workshop 3

Sorting Algorithms

Build programs to sort arrays of 32-bit integers using:
1. quicksort (use the standard library function qsort unless you think that you can do better!)

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!

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.

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.

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.

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!

Due Date

Monday, October 20, 5pm