1 Preamble
Data Structures and Algorithms
Assignment Semester 1, 2019 v1.0
Department of Computing Curtin University
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 – if in doubt, ask.
2 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.
3 Submission
Submit electronically via Blackboard. Make sure to submit early. You can submit multiple times – we will only mark the last attempt. Take care not to submit your last version late though. Read the submission instructions very carefully.
You should submit a single file, which should be zipped (.zip) or tarred (.tar.gz). Check that you can decompress it on lab machines. These are also the computers that your work will be tested on, so make sure that your work runs there. The file must be named DSA_Assignment_
The file must contain the following:
• Your code. This means all files needed to run your program. Do not include any .class files. Do include input files used as part of the assignment if that is required to run your program.
• README file including short descriptions of all files and dependencies, and information on how to run the program.
• Your unit test harnesses for each class/ADT. One of the easiest ways for us to be sure that your code works is to make sure that you’ve tested it properly. Our test harnesses may not work for some of your classes and you may have classes that we’re not specifically asking
Remember : Think before you code!
for, so make it easy for us to test your work. A test harness for class/module X should be
called UnitTestX/ModuleTestX.
• Documentation and Report for your code, as described in Section 3.1.
• A signed and dated cover sheet. These are available from the [[Computing Colloquium]]
Blackboard unit or from the Computing reception (building 314, 3rd floor). You can sign a
hard copy and scan it in or you can fill in a soft copy and digitally sign it.
• Java students:
o You may include a Makefile, but this is not required. We will use javac *.java to compile your files and run the unit tests by their expected names.
o Do not include .class files or anything else that we do not need. We will compile your .java files to ensure that what we’re testing is what we’re reading.
Make sure that your file contains what is required. Anything not included in your submission will not be marked, even if you attempt to provide it later. It is your responsibility to make sure that your submission is complete and correct.
3.1 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.
3.2 Marking
Marks will be awarded to your submission as follows:
• [10 marks] Documentation. This is mainly things like choosing and justifying your structure, ADTs, and algorithms. Note that you will only get these marks if you adequately justify your decisions and properly implement them. So, for example, if you choose an algorithm and adequately justify it but aren’t actually able to implement it you’ll only get part of the marks.
• [30 marks] Code testing. We’ll have a number of tests to run, and you get marks proportional to how many tests your code passes. If your code passes all of the tests, then you will get all of these 30 marks.
• [30 marks] Implementation. We will use unit testing as well as looking at code quality; your test harnesses will have a big impact on these marks. Students are encouraged to use testing frameworks for their harnesses.
• [30 marks] Profiling report. As described in section 3.1, with the majority of marks for the methodology and results sections.
• Marks will be deducted for not following specifications outlined08 in this document, which includes incorrect submission format and content and using built-in Java ADTs.
• If the cover sheet isn’t provided with your submission, your submission will not be marked and you will be awarded zero (0) marks. If you forget to submit the cover sheet you will be allowed to submit it separately to the unit coordinator (by e-mail or in person) but will lose 5 marks.
The aims of this marking breakdown is as follows:
• To reward you for good design decisions, but not unless you’re able to implement them. This is the core aim of the unit.
• To let you score some marks if you get the program working but make with poor decisions. If all of your decisions are based only on ease of implementation you can still score the 30 marks from the implementation category and will score most of the marks from testing, meaning you can pass if all of your code works perfectly and is of sufficient quality. It’s taking a risk, though.
• To promote good testing. Industry is repeatedly telling us they are really looking for students who can properly test their code.
• To teach you to follow specifications carefully.
• To reward students who have been serious about doing their practical work.
3.3 Requirements for passing the unit
Please note: As specified in the unit outline, it is necessary to have attempted the assignment in order to pass the unit. As a guide, you should score at least 15% to be considered to have attempted this assignment. We have given you the exact mark breakdown in Section 3.2. Note that the marks indicated in this section represent maximums, achieved only if you completely satisfy the requirements of the relevant section.
Plagiarism is a serious offence. This assignment has many correct solutions so plagiarism will be easy for us to detect (and we will). For information about plagiarism, please refer to http://academicintegrity.curtin.edu.au.
In the case of doubt, you may be asked to explain your code and the reason for choices that you have made as part of coding to the unit coordinator. A failure to adequately display knowledge required to have produced the code will most likely result in being formally accused of cheating.
Finally, be sure to secure your code. If someone else gets access to your code for any reason (including because you left it on a lab machine, lost a USB drive containing the code or put it on a public repository) you will be held partially responsible for any plagiarism that results.
3.4 Late Submission
As specified in the unit outline, you must submit the assignment on the due date. Acceptance of late submissions is not automatic and will require supporting documentation proving that the late submission was due to unexpected factors outside your control. See the unit outline for details as to the procedure for requesting that an assessment be accepted after the due date.
Note that external pre-scheduled commitments including, but not limited to, work, travel, scheduled medical, sporting, family or community engagements are not considered unexpected factors outside your control. If you know you have, or are likely to have, such engagements and that they may affect your ability to complete the assignment, you will be expected to have planned your work accordingly. This may mean that you need to start and/or complete your assignment early to make sure that you are able to hand it in on time.
Also note that IT related issues are almost never a valid excuse. These include computer crashes, hard disk corruption, viruses, losing computers/storage media, networks going down (even if it is Curtin’s network – outages of the entire Curtin network of more than 24 hours may be considered depending on circumstances) or the like. As IT professionals in training, you are expected to have suitable backups and alternative ways of getting your assignment completed in the event that any IT problems are encountered. You are also expected to submit your assignment ahead of time to allow for unforeseen issues.
In the event that you submit your assignment late and are deemed to have a valid excuse, you will be penalised 10% (that is, 10% out of 100%, not out of what you would have received) per calendar day that you are late, up to a maximum of seven (7) calendar days. Any work submitted after this time will not be marked and you will automatically fail the unit. Note that if you are granted an extension you will be able to submit your work up to the extended time without penalty – this is different from submitting late.
Note that the requirements for passing this unit are applied after penalties. An assignment normally scoring 20% that is submitted one day late, even with a valid excuse, will score only 10% and thus not satisfy the requirements for passing this unit.
3.5 Clarifications and Amendments
This assignment specification may be clarified and/or amended at any time. Such clarifications and amendments will be announced in the lecture and on the unit’s Blackboard page (not necessarily at the same time and not necessarily in that order). These clarifications and amendments form part of the assignment specification and may include things that affect mark allocations or specific tasks. It is your responsibility to be aware of these, either by attending the lectures, watching the iLecture and/or monitoring the Blackboard page.