- 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.

simple copies of other people's code are unlikely to gain much credit.

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.

- 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.

- 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.

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

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!

The algorithm in Cormen (and some other texts) is not the most efficient: implement

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!

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 -