JavaLinked Binary Tree.
Specification of the coding
Description
This assignment involves manipulating binary trees which represent arithmetic expressions. The binary trees are implemented by the LinkedBinaryTree class provided by the textbook, which we have put in a textbook package in the source code. We have made one small modification to the code, to remove the implementations of some standard tree traversals. If you choose to use tree traversals as part of your solution, you will need to implement them yourself in Assignment.java instead.
The only file which you should edit is Assignment.java, which contains a class Assignment, which implements a number of static methods working with binary trees. The following methods are required:
Each of these methods is described by a more detailed comment in the code, and has some examples of input/output later in this document.
You can (and should) add private static helper methods as needed. Note that all of the methods in this class should be static methods (meaning that you do not need to instantiate the class to use them.)
For all the methods except isArithmeticExpression, an IllegalArgumentException should be thrown if an invalid argument is used (i.e. if the tree is null or not an arithmetic expression, or if we try to set a value to null.)
The first two methods, prefix2tree and equals have been implemented for you:
- prefix2tree takes an arithmetic expression in prefix notation (also known as Polish notation) and builds a linked binary tree, using the textbook’s implementation
LinkedBinaryTree, which is included in the code base in the package textbook. This should be very helpful for your testing, as it makes it very easy to build valid trees, as well as giving you an example of using one of the most useful LinkedBinaryTree methods, attach. - equals takes two trees and decides if they are the same (i.e. they have the same structure and every node has the same value.) You may find this useful during testing.
Recursion
We strongly encourage you to implement most of the methods recursively. There will be at least one question in the exam which will be much easier to answer recursively than iteratively, so this is a great opportunity to get some more practice with recursion.
If you would prefer to iterate over some sort of tree traversal for some of the methods, you may do so, although you will need to implement the appropriate traversal(s) yourself in the Assignment class, as we have removed them from the textbook tree implementations.
Notation
Values and variables
Any strings which are integers are values. Anything that is not an integer or an operator (see below) is to be considered a variable (although in the automarking we will only use single letters for variable labels, i.e. “x”, “c”, etc.)
Operators
Our operators are all binary operators (they take exactly two operands.) We will support +, - and * only (i.e. you do not need to implement division). Operands are always either numbers, or are variables. Any string which is not an integer or decimal number is to be considered a variable.
Infix notation (parenthesised)
Infix is the notation you are probably most familiar with. Infix notation puts binary operators (such as +, - and *) in between their operands, and uses parenthesis to show the order in which the operators should be applied. For this assignment we will strictly include the parenthesis even when we would normally omit them (for example, it’s obvious that 1 * 3 + 4 - 2 = 5, but your tree2infix method should write this as ((1 * 3) + (4 - 2))).
Prefix notation (without parenthesis)
Prefix notation is where the arithmetic operators are written before their operands. For example adding one and two in prefix notation is + 1 2. Because we know in advance how many operands each operator uses, we will never use parenthesis to show precedence (note: we are only using - as a binary operator. If we want to take the negative of a variable x, we’d have to write - 0 x to subtract it from zero.n
Specification of the report
You must write a short report, and submit it via Turnitin. The report contains the following sections
- Description and justification of the tests you have written. Each test should be described to say what the input and expected output are, and what the purpose of this test is.
- Analysis of run-time cost. For each public method, you should describe the algorithm you intend to use for this, and state the big-Oh worst-case runtime, in terms of the length of the arithmetic expression, the height of the tree, or other important aspects of the input data. You should also give a short justification of this cost, for example, by indicating how much of the tree is examined, and how much work is done on each node.
- If you are a postgraduate student enrolled in INFO9105, also describe some extra methods you would propose to extend the functionality of the system. Explain what each proposed method would do (it would help to give examples of input and output, as we do for methods such as substitute above), and how this could be useful.
Marking
Code automarking
Part of the marking of your code will be done automatically on Ed. You are encouraged to submit early and often - there is no penalty for making multiple submissions.
There will be some visible tests to help you verify that your solution is configured correctly. The remaining test cases will be invisible until after the submission deadline. Test your code carefully to ensure that your solution works correctly. The score on this component will be based on the number of tests passed. If you pass every visible test, you will get at least half of the available marks.
Code quality
Part of the marking of your code will be done by hand. We will grade your code on its readability and overall quality. Your code should be well laid out, with appropriate use of whitespace. Comments should be used where it makes your code easier to understand.
Variables and methods should be named appropriately. If appropriate, helper methods should be used to avoid duplicating code, and to make any very complex methods easier to understand.
- Pass level: You have implemented several of the methods in a sensible way. Most of the code is understandable without particular effort, with mostly sensible layout, and meaningful comments where needed.
- Distinction level: As for Pass, and you have implemented most of the methods required in ways that avoid any serious inefficiency, and the code is easy to follow, helping the reader and avoiding distraction (this implies that the code is well-structured with appropriate use of helper methods; it has a good choice of layout and comments, well chosen names; and idiomatic use of Java language).
Testing
This is based on your report (where the tests are described and justified), and on examination of the code (where the tests are written). Note that you can gain these marks even if the code of the methods doesn’t work correctly or even compile, as long as tests are written properly.
- Pass level: There is a reasonable range of tests for normal cases of the public methods, which are provided in the submitted code and are listed in the report.
- Distinction level: As for Pass, and also the tests are done in JUnit, they are well chosen and justified, covering a significant range of both normal and corner cases.
Analysis of worst-case runtime
This is based on your report. Note that you can gain these marks even if you didn’t write any code, as long as you analyse algorithms that you describe in the report, intended to operate on the binary tree.
- Pass level: For several of the public methods, you describe a reasonable algorithm for the task, and you state the correct big-Oh for its worst-case running time.
- Distinction level: For most of the public methods, you describe a reasonable algorithm for the task, and you state the correct big-Oh for its worst-case running time, and you provide convincing and valid arguments that justify your claim about the cost.
Proposals for additional methods
Note that this is only needed from postgraduate students who are enrolled in INFO9105. Undergraduate students do not write this discussion. This is based on your report, where you are asked to describe some extra public methods that could be useful, if added to those that are described in the assignment. Note that you can gain these marks even if you didn’t write any code, as long as you propose some interesting methods that could provide useful extra functionality for this system.
- Pass level: Your report clearly describes a method that provides functionality not available in the system described in the assignment (the functionality needs to be understandable by the reader).
- Distinction level: Your report clearly deescribes at least four methods that each provide additional functionality not available in the system described in the assignment or through use of the other methods proposed (the functionality of each needs to be understandable by the reader), and you show how each could be useful.