Data Structures and Algorithms

Assignments 3 & 4 - 1999

Algorithm Implementation and Verification

The basic aims of this assignment are to

give you some experience in implementing an algorithm of reasonable complexity
ensure that you understand how to rigorously verify that a function is correct and
determine its time complexity.

For variety - and to give you some practical exposure to more than one algorithm - you will implement an algorithm chosen as specified below as your assignment 3 exercise and test another one (which you will obtain from a class-mate who has completed it for assignment 3) for your assignment 4.

The list of algorithms to be implemented (and verified) are:

Hash Table Lookup,
Radix Sort,
Fast Fourier Transform,
Dijkstra's Algorithm,
Kruskal's Algorithm,
Prim's Algorithm,
Optimal Binary Search Tree,
Matrix Chain Multiplication.
Red-Black tree,
AVL-tree,

Code - of varying degrees of suitability - may be found for most of these either in textbooks or on the Web.

You will need to take that code and re-work it into a suitable class structure:
simple copies of other people's code are unlikely to gain much credit. For sorting and searching algorithms, obviously an extension of the Collection class will work well. For graph algorithms, then you should make a general-purpose Graph class. For the FFT, a class of numerical datasets, called something like DataSet would do: although you could probably use the Collection class also. Matrix chain multiplication is obviously a method on a class of matrices which takes an array of matrices and works out how to most efficiently multiply them, then multiplies them! However, it is likely that you will be able to use someone else's code very effectively by simply "wrapping" it in an appropriate method.

It makes sense to team up with one other member of the class so that you can exchange code that you have written for assignment 3 to do assignment 4. You must verify and measure the time complexity of a different algorithm from the one you implemented for assignment 3.

Language

It is required that you use a language with a suitable standard. (Suitable means approved by a recognised standards body - not a so-called industry standard!). ANSI standard C is the obvious candidate. However, algorithms coded in Java are acceptable. (C++ will be allowed if you can convince us that you know enough about the ANSI standard to follow it faithfully! The final approval was in November, 1997. So, if you have a copy of the C++ standard and can convince me that your program conforms to it, I will accept it!) Java also has an ISO standard now and will be allowed for those who want to get some practice with it.

Preliminary Submission

In order that you can get fixed and stable specifications of the class containing the method you'll be verifying for assignment 4, you are required to submit - for feedback and approval only - a copy of the specifications of any classes that you will be implementing in mid-September. These specifications will be checked and approved so that

you can proceed with confidence,
your partner, who needs a concrete specification of your class to design and write verification and timing programs, can proceed.

This preliminary submission will not be marked and you will have a chance to correct any shortcomings, but you will be penalised if it is late - as another member of the class is probably depending on it. Only the specifications are needed - well annotated .h file(s). However, you may submit for comment anything that you have done up to that point.

Report

Assignment 3

Since someone else is going to perform some rigorous tests on your algorithm, you only need to perform some rudimentary tests yourself. It would be extremely unprofessional to hand over for verification something that you had not tested yourself at all! Your assignment 3 report should include, as a minimum,

brief description of the structure of your code,
suitable references or acknowledgments for any code that you might have obtained (in any form) from others and
a brief description of your preliminary tests.

If your class-mate has finished the verification of your code before you need to submit, then it will do no harm to submit his or her "test certificate" (ie report) along with your submission in order to strengthen your case for a good mark. However, the markers will generally try to pair up code and tests in their assessment of submissions.

Assignment 4

This report will need to be reasonably substantial as it will need to describe the analysis of the algorithm tested for equivalence classes, the results of the tests (hopefully all as expected!) and the time complexity measurements.

The report should be plain ASCII text - not the native form of any word processor.

Choosing your algorithm

Use the second last digit of your student number (ie leaving out the final check digit), choose the appropriate algorithm from the numbered list (or the radix sort challenge!). If your number is xxxxx0x, your problem number is 10. For testing, you can team up with anyone doing a different algorithm for assignment 3. If you have problems (your original team-mate withdraws, gets a job with a six-digit income, breaks a leg, etc), you can obtain the same, or any other algorithm, from someone else.

Special Challenges

Radix Sort

The challenge of designing a practical, general-purpose radix sort that runs faster than the library quicksort is open to any one. General-purpose means that, just like our collections that support sorts and searches on items with any form of key, so your radix sort should also support any set of radices for the keys of items to be sorted. If you're attempting this challenge and you're unsure of the significance of this, it would probably be a good idea to seek advice.

Bonus: 1.5 times your mark for assignment 3 if you can demonstrate that your radix sort is really faster than the library quicksort on random data that I will generate!

Red-black and AVL trees

For a team of three:
The algorithm in Cormen (and some other texts) is not the most efficient: implement both Cormen's version and that found in Weiss' text as well as AVL trees. Three algorithms or variants = three people!

Bonus: 1.5 times for the team if you can produce three pieces of code in a consistent style (to make comparisons valid) and, as part of your verification exercise, show exactly how efficient each one is. Obviously, to get the full 1.5 bonus, your report needs to have some intelligent analysis of the differences (if any) observed!

Quick sorting

We would expect the library implementation of quick sort to be pretty damned quick - certainly faster than a naively coded C variant. Can you code yourself a version of qsort that is as good as the library versions?

Bonus: 1.5 times if you're faster than the library quicksort on at least two different machines and you produce a report showing how various speedup efforts improved the performance. 1.4 times if you're close on two machines without resorting to assembler - ie the same code is used on both machines!

Prim's and Kruskal's Algorithms

Various improvements over the 'standard' algorithms are known. If you can implement one successfully, and demonstrate that it's faster than somebody else's standard one, a bonus of 1.5 will apply also!