Introduction
In practicals you have implemented and learned about a number of algorithms and ADTs and will be
implementing more of these in the remaining practicals. In this assignment, you will be making use
of this knowledge to implement a system to explore and compare a variety of ADT implementations.
Feel free to re-use the generic ADTs from your practicals. However, remember to self-cite; if you
submit work that you have already submitted for a previous assessment (in this unit or any other)
you have to specifically state this. Do not use the Java implementations of ADTs
The Problem
Over the semester we have been discussing the relative performance of various ADTs. In the Sorting
practical, we were able to see this in action with the
SortsTestHarness. Your mission in this
assignment is to implement, compare and report on a series of
tree
implementations. The trees
must include:
A Binary Search Tree
A B-tree with the option to vary the number of keys per node (e.g. 3, 7, 19)
An additional tree ADT implementation of your choice
Note: all trees must have insert, find and delete methods.
Your program should be called
TreeProfiler, and have three starting options:
No command line arguments : provides usage information
"-i" : interactive testing environment
"-p" : profiling mode
When the program starts in interactive mode, it should show the following main menu:
(1) – Load new data
(2) – Tree find
(3) – Tree insert
(4) – Tree delete
(3) – Tree statistics
(4) – Save tree
(0) – Quit
Choice:>
The user enters in their choice and the system executes the desired option (possibly involving
further user input). Statistics will be displayed to screen with an option to save to file. After the
option has completed processing, the main menu should be re-displayed. In other words, make each
option its own method, and call this from a mainMenu() (or similar) method that executes a loop
until the Quit option is made.
Statistics:
Size : Number of elements in tree.
Height : Based on longest path
Balance : create a measure of how balanced the tree is. Output as percentage (0-100%)
Any other statistics/characteristics you find useful
Saving the tree should give the option of a text output in sorted order, or a serialised, binary export.
Loading should be able to read either of these files, as well as the stock data.
Profiling mode
should allow the choice of tree, data size and input file (on the command line); and
output only the statistics and any other information that may assist understanding and decisions for
the report. Look at the code provided for the Sorting practical for inspiration (citing it as required, of
course).
Sample data
will be taken from the Stock Exchange data used in Practical 1. To gain access to a large
amount of data to test your code, go to the archives at https://www.asxhistoricaldata.com/. This is
the file format to set up your code to work with.
Documentation and Report
You need to submit your documentation and report in docx or pdf format.
Your Documentation will be minimum 2-4 pages (excluding UML and Javadocs) and should include
the following:
An
overview
of your code, explaining any questions that the marker may have. This is
supplemented by the comments in your code. In general, if the marker is looking at your
code and isn’t sure why you have done something in that particular way, they will check
your documentation to see if they can find an explanation. Using an automated
documentation system like Javadocs may be very helpful. It is not required, though.
A
UML diagram
of your code.
A description of any
classes
you have, you need to let us know not only what the purpose of
that class is but why you chose to create it. As part of this, also identify and justify any places
where it was possibly useful to create a new class but you chose not to, especially when it
comes to inheritance.
The Report will follow the structure of a standard academic report or paper. It should be at least 4-6
pages long. Required sections are:
Abstract:
Explain the purpose of the report and state the trees that you will be assessing,
and the outcomes/recommendations.
Background:
Discuss your choice of trees, their similarities and differences.
Methodology:
Describe how you have chosen to profile and compare the trees, and why.
Include the commands, input files, outputs – anything needed to reproduce your results.
Results:
Present the results of your profiling.
Conclusion and Future Work:
Give your conclusions and what further investigations could
follow.