Description
Question 1(a) [1 mark]:
Class part1.ArrayStack (that is, class ArrayStack in the part1 package) is an
implementation of the adt.IStack interface.
Using the JUnit tests in part1.test.ArrayStackTest discover and correct the 2
ERRORS in the part1.ArrayStack implementation of the adt.IStack interface.
When you find an error, insert a brief one-line “//” comment at that location, indicating where
the error had been found, and why it occurred.
You may not modify the code other than to fix the 2 ERRORS and insert the required
comments.
Question 1(b) [2 mark]:
Class part1.LinkedList is a doubly-linked list implementation of the
adt.PositionList interface, that does not use header and trailer sentinels. It uses the
part1.Node implementation of the adt.Position interface.
Using the JUnit tests in part1.test.LinkedListTest discover and correct the 4
ERRORS in the part1.LinkedList implementation of the adt.PositionList
interface. When you find an error, insert a brief one-line “//” comment at that location,
indicating where the error had been found, and why it occurred.
You may not modify the code other than to fix the 4 ERRORS and insert the required
comments. Do not modify part1.Node in any way.
COMP3506/7505, The University of Queensland. 2
Part 2: Trees [12 marks for COMP3506, 15 marks for COMP7505]
The purpose of this part of the assignment is for you to gain experience writing and analysing
tree algorithms.
Types of expenditure for an organisation can be classified using a hierarchical classification
scheme. In Figure 1, for instance, we give a simplistic example of how expenditures for a
university could be classified.
Figure 1: A simple hierarchical classification scheme of expenditures for a university.
In general, such a classification scheme is described as a tree, where each node can have
either zero, one or more children. Each node represents a type of expenditure, which is a
subtype of its parent, if any, and of its other ancestors. For example, in Figure 1,
Disadvantaged Student Scholarship expenses are a subtype of Scholarship expenses, which is
itself a subtype of all University Expenses. Each type of expenditure can only appear once in a
classification tree. For instance, there couldn’t be two different nodes in the tree with the
name Research Infrastructure.
When donations are made to an organisation, it is typical for the donor to specify the types of
expenditures that donation can be used for with respect to that organisation’s expenditure
classification scheme. For instance, a donor to a university using the scheme in Fig. 1 may
specify that their donation may be used for Scholarships, Sporting Facilities or Research
Infrastructure.
If such a donation can be used for a particular type of expense, then it may implicitly be used
for any subtype of that expense. For example, if a donation can (w.r.t. Fig. 1) be spent on
Grounds, then it can be used for any expense classified more specifically as either Sporting
Facilities, Parking Facilities, Other Facilities, Tennis Facilities, Swimming Facilities,
Athletics Facilities, or Other Sporting Facilities. Also, if a donation may be used for every
subtype of an expense type, then it may also be used for that type itself. For example, a
donation (w.r.t. Fig.1) that could be spent on Tennis Facilities, Swimming Facilities, Athletics
Facilities or Other Sporting Facilities could be used to fund any project classified more
generally as a Sporting Facility (since a Sporting Facility expense must be one of those four
kinds of expenses according to the tree).
COMP3506/7505, The University of Queensland. 3
Given a set S of types of expenses that a donation can be spent on we refer to the closure of
S, written as closure(S), to be the set of all types of expenses that that donation can be spent
on. The closure is taken with respect to the relevant classification tree. For example, for the
tree in Fig. 1 we have that
closure({Scholarships, Grounds and Infrastructure})
=
closure({Disadvantaged Student Scholarships, Scholarships, Athletics Facilities,
Sporting Facilities, Parking Facilities, Other Facilities, Research Infrastructure,
Teaching Infrastructure })
=
{Other Student Scholarships, Disadvantaged Student Scholarships, Scholarships,
Tennis Facilities, Swimming Facilities, Athletics Facilities, Other Sporting Facilities,
Sporting Facilities, Parking Facilities, Other Facilities, Grounds, Research
Infrastructure, Teaching Infrastructure, Grounds and Infrastructure}
When donors specify the types of project that their donation may be spent on they are not
always as concise as they could be. For instance, a donation that could be spent on either
Disadvantaged Student Scholarships, Scholarships, Athletics Facilities, Sporting Facilities,
Parking Facilities, Other Facilities, Research Infrastructure or Teaching Infrastructure
(w.r.t. Fig. 1), could more concisely be described as a donation that could be spent on
Scholarships or Grounds and Infrastructure.
Given a set S of expense types from a classification tree, that is used by a donor to describe
the types of expenditures that a donation may be used for, we define the summary of that set
S to be the smallest set X of expense types from the classification tree such that
1) the closure of S equals the closure of X
2) for each type y in the closure of S, either y is in X or an ancestor of y is in X.
Using this terminology we have that the summary of S = {Disadvantaged Student
Scholarships, Scholarships, Athletics Facilities, Sporting Facilities, Parking Facilities, Other
Facilities, Research Infrastructure, Teaching Infrastructure} is X = {Scholarships, Grounds
and Infrastructure} with respect to the classification scheme in Figure 1.
We say that a set S of expenditure types is concise with respect to a classification tree, if the
summary of S equals S.
Some donors chose to describe what their donation may be spent on by giving a list of
expenditure types that they forbid their money to be spent on.
We define the negation of a set of expenditure types S to be the concise set X such that the
closure of X contains all of the types in the given classification scheme tree other than those
types that are either in the set S, or are an ancestor or descendent of an element of S.
For example, the negation of the set {Parking Facilities, Scholarships} is the concise set
{Salaries and Wages, Sporting Facilities, Other Facilities, Research Infrastructure, Teaching
infrastructure}.
COMP3506/7505, The University of Queensland. 4
Question 2(a)[2 marks]:
Implement method summary in the class part2.ExpenditureTrees efficiently
according to its specification in that file.
You may use the linear data structures in java.util from the Java 7 SE API in your
implementation (e.g. ArrayList, LinkedList, ArrayDeque etc.), but no other libraries should be
used. (It is not necessary and makes marking hard.)
You may write supporting methods, but they must be declared private and included in the
part2.ExpenditureTrees file. Similarly, if you choose to write any supporting
classes, then they must be written as private nested classes and included in that file.
To help you get your solution right, you should write you own JUnit tests in
part2.test.ExpenditureTreeTest (some basic tests are included to get you
started). Tests that you write will not be marked. We will test your implementation with our
own tests.
Question 2(b)[2 marks]:
Let n be the number of nodes in the hierarchical classification scheme tree of
expenditures, m be the number of expenditure types in the parameter list types, and p be the
maximum length of any string used to represent an expenditure type in the tree. What is the
worst-case time complexity and the worst-case space complexity of your summary method
in terms of n, m and p? Justify your answer.
Express your answers in big-Oh notation, making the bounds as tight as possible, and
simplifying your answer as much as possible.
(N.B. The space complexity of your method should be measured in terms of how much
additional space your method consumes. It does not include the space already consumed by
the method parameters.)
Question 3(a)[2 marks]:
Implement method contains in the class part2.ExpenditureTrees efficiently
according to its specification in that file.
You may use the linear data structures in java.util from the Java 7 SE API in your
implementation (e.g. ArrayList, LinkedList, ArrayDeque etc.), but no other libraries should be
used. (It is not necessary and makes marking hard.)
You may write supporting methods, but they must be declared private and included in the
part2.ExpenditureTrees file. Similarly, if you choose to write any supporting classes,
then they must be written as private nested classes and included in that file.
To help you get your solution right, you should write you own JUnit tests in
part2.test.ExpenditureTreeTest (some basic tests are included to get you
started). Tests that you write will not be marked. We will test your implementation with our
own tests.
Question 3(b)[2 marks]:
Let n be the number of nodes in the hierarchical classification scheme tree of expenditures,
and m be the number of expenditure types in the parameter list types. Assuming that the
length of each string used to represent an expenditure type in the tree is bound above by
log2n, what is the worst-case time complexity and the worst-case space complexity of your
contains method in terms of n and m? Justify your answer.
COMP3506/7505, The University of Queensland. 5
Express your answers in big-Oh notation, making the bounds as tight as possible, and
simplifying your answer as much as possible.
(N.B. The space complexity of your method should be measured in terms of how much
additional space your method consumes. It does not include the space already consumed by
the method parameters.)
Question 4(a)[2 marks]:
Implement method negation in the class part2.ExpenditureTrees efficiently
according to its specification in that file.
You may use the linear data structures in java.util from the Java 7 SE API in your
implementation (e.g. ArrayList, LinkedList, ArrayDeque etc.), but no other libraries should be
used. (It is not necessary and makes marking hard.)
You may write supporting methods, but they must be declared private and included in the
part2.ExpenditureTrees file. Similarly, if you choose to write any supporting
classes, then they must be written as private nested classes and included in that file.
To help you get your solution right, you should write you own JUnit tests in
part2.test.ExpenditureTreeTest (some basic tests are included to get you
started). Tests that you write will not be marked. We will test your implementation with our
own tests.
Question 4(b)[2 marks]:
Let n be the number of nodes in the hierarchical classification scheme tree of
expenditures. Assuming that the length of each string used to represent an expenditure type in
the tree is bound above by log2 n, what is the worst-case time complexity and the worstcase space complexity of your negation method in terms of n? Justify your answer.
Express your answers in big-Oh notation, making the bounds as tight as possible, and
simplifying your answer as much as possible.
(N.B. The space complexity of your method should be measured in terms of how much
additional space your method consumes. It does not include the space already consumed by
the method parameters.)
Question 4(c)[3 marks]: COMP7505 ONLY:
Perform an experimental analysis of the worst-case running time of your method negation,
given that the length of each string used to represent an expenditure type in the tree is bound
above by log2 n, where n is the number of nodes n in the parameter tree.
Using the method System.currentTimeMillis(), you should measure the running
time of your method negation for a suitably large range of inputs. Chose inputs for which
your algorithm should exhibit worst-case behaviour. Use your results to plot a graph of
measured running time against input size, where you measure the input size of the program in
terms of the number of nodes n in the parameter tree. Clearly label the axes of your graph.
Explain whether or not your experimental analysis confirms your theoretical analysis from
Q4(b) of the worst-case running time of this method. If there is a discrepancy between your
theoretical and experimental result, discuss why that might be the case.
Explain how you collected your results. As part of this explanation, include a copy of your
code that you used to run the experiment (so that we can see how you did it).
COMP3506/7505, The University of Queensland. 6
Practical considerations:
If necessary, there may be some small changes to the files that are provided, up to 1 week
before the deadline, in order to make the requirements clearer, or to tweak test cases. These
updates will be clearly announced on the Announcements page of the course Blackboard site,
and during the lectures.
For the coding tasks:
• Don’t change the class names, specifications provided, or alter the method names,
parameter types or return types or the packages to which the files belong.
• Don’t write any code that is operating-system specific (e.g. by hard-coding in newline
characters etc.), since we will batch test your code on a Unix machine.
• Your source files should be written using ASCII characters only.
Submission: Submit each of your source code files ArrayStack.java,
LinkedList.java, ExpenditureTrees.java as well as your written answers to
questions 2(b), 3(b), 4(b) [and 4(c) if you are COMP7505] in report.pdf electronically
using Blackboard according to the exact instructions on the Blackboard website:
https://learn.uq.edu.au/
Answers to each of the questions 2(b), 3(b), 4(b) [and 4(c) if you are COMP7505] should be
clearly labelled and included in file report.pdf.
You can submit your assignment multiple times before the assignment deadline but only the
last submission will be saved by the system and marked. Only submit the files listed above.
You are responsible for ensuring that you have submitted the files that you intended to submit
in the way that we have requested them. You will be marked on the files that you submitted
and not on those that you intended to submit. Only files that are submitted according to the
instructions on Blackboard will be marked.
COMP3506/7505, The University of Queensland. 7
Evaluation: Your assignment will be given a mark according to the following marking
criteria. For COMP3506 the total marks possible is 15, and for COMP7505 the total marks
possible is 18. The assignment is worth 15% for both courses.
Code must be clearly written, consistently indented, and commented. Java naming
conventions should be used, and lines should not be excessively long (> 80 chars). Marks will
be deducted in code analysis questions if we cannot read and understand your solution to
check your analysis.
Part 1
Q1(a) [1 mark]:
• solution compiles and passes ALL part1.test.ArrayStackTest tests, and location and
cause of all errors correctly marked 1 mark
• otherwise or work has no academic merit 0 marks
Q1(b) [2 marks]:
• solution compiles and passes ALL part1.test.LinkedListTest tests, and location and
cause of all errors correctly marked 2 marks
• otherwise or work has no academic merit 0 marks
Part 2
Q2(a)[2 marks]:
Given that the solution does not violate any restrictions (using forbidden libraries etc), [0.5
marks] will be allocated for efficiency and the remaining [1.5 marks] will be allocated based
on the outcome of running test cases:
• All of our tests pass 1.5 marks
• At least 2/3 of our tests pass 1 marks
• At least 1/3 of our tests pass 0.5 marks
• Work with little or no academic merit 0 marks
Note: code submitted with compilation errors will result in zero marks in this section. Code
that violates any stated restrictions will receive zero marks.
Q2(b)[2 marks]
Time analysis is correct and justified. [1 mark]
Space analysis is correct and justified. [1 mark]
A mark of 0 will be given for this part if no reasonable attempt was made to complete part (a)
or the solution to part (a) is obviously incorrect or difficult to read and comprehend.
COMP3506/7505, The University of Queensland. 8
Q3(a)[2 marks]:
Given that the solution does not violate any restrictions (using forbidden libraries etc), [0.5
marks] will be allocated for efficiency and the remaining [1.5 marks] will be allocated based
on the outcome of running test cases:
• All of our tests pass 1.5 marks
• At least 2/3 of our tests pass 1 marks
• At least 1/3 of our tests pass 0.5 marks
• Work with little or no academic merit 0 marks
Note: code submitted with compilation errors will result in zero marks in this section. Code
that violates any stated restrictions will receive zero marks.
Q3(b)[2 marks]
Time analysis is correct and justified. [1 mark]
Space analysis is correct and justified. [1 mark]
A mark of 0 will be given for this part if no reasonable attempt was made to complete part (a)
or the solution to part (a) is obviously incorrect or difficult to read and comprehend.
Q4(a)[2 marks]:
Given that the solution does not violate any restrictions (using forbidden libraries etc), [0.5
marks] will be allocated for efficiency and the remaining [1.5 marks] will be allocated based
on the outcome of running test cases:
• All of our tests pass 1.5 marks
• At least 2/3 of our tests pass 1 marks
• At least 1/3 of our tests pass 0.5 marks
• Work with little or no academic merit 0 marks
Note: code submitted with compilation errors will result in zero marks in this section. Code
that violates any stated restrictions will receive zero marks.
Q4(b)[2 marks]
Time analysis is correct and justified. [1 mark]
Space analysis is correct and justified. [1 mark]
A mark of 0 will be given for this part if no reasonable attempt was made to complete part (a)
or the solution to part (a) is obviously incorrect or difficult to read and comprehend.
Question 4(c)[3 marks]: COMP7505 ONLY:
[2 marks] will be allocated for providing and properly graphing experimental results (for a
range of well-chosen inputs) that were collected using the method you explained (including
code). If it is not clear how you obtained your data, then no marks will be given for this part.
[1 mark] will be allocated for providing a valid comparison of your experimental and
theoretical analysis, including an explanation of any apparent discrepancies between them.
A mark of 0 will be given for this part if no reasonable attempt was made to complete part (a)
or the solution to part (a) is obviously incorrect or difficult to read and comprehend.
COMP3506/7505, The University of Queensland. 9
School Policy on Student Misconduct: You are required to read and understand the School
Statement on Misconduct, available on the School’s website at:
http://ppl.app.uq.edu.au/content/3.60.04-student-integrity-and-misconduct
This is an individual assignment. If you are found guilty of misconduct (plagiarism or
collusion) then penalties will be applied.
If you are under pressure to meet the assignment deadline, contact the course coordinator as
soon as possible.