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,
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
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
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
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.
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.
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
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
- you can proceed with confidence,
- your partner, who needs a concrete specification of your
class to design and write verification and timing programs,
Since someone else is going to perform some rigorous tests
on your algorithm, you only need to perform some rudimentary
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,
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.
- 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.
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
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!
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!
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
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!
If you expect an HD, then I will provide you with an appropriate
bonus challenge for any problem if requested.
Submission Instructions will be available soon!