Description
Problem overview:
The University of Woolloomooloo receives donations from which it is able to fund a number
of projects, such as building a new library, repairing the façade of a heritage building, paying
for scholarships etc. Each donation is conditional, in that it may only be spent on projects
approved by the donor. Having so many donations, but also so many projects to undertake,
the University has recently got itself into some strife: having committed to fund projects that
it cannot afford, given their existing donations and the conditions upon them. Not wanting to
make the same mistake twice, they want some software that can help them determine whether
or not they can completely fund a set of projects, given the conditional donations that are
available to them. If they are able to completely fund the set of projects, they want to know
how to allocate funds to those projects from their pool of donations.
More specifically, the University of Woolloomooloo wants a program that takes a list of
donations and a set of projects as input where:
• each donation has a unique name, a total donation amount (in whole dollars) and a set
of projects that the donation may be spent on. Initially, no dollars from any of the
donations have been spent.
• each project has a unique name, a total cost, and initially has no allocated funds. The
total cost of a project is in whole dollars.
and either
• returns false if there no way to completely fund all of the given projects using the
donations, leaving both the input list of donations and set of projects unmodified;
• or otherwise returns true and allocates to each project funding from the donations.
The allocation to each project must be complete (accounting for the entire cost of that
project exactly), and it may not violate the conditions of the donations (e.g. you can
only allocate money from a donation to the projects that it may be spent on). The
unspent funds in each donation should reflect the allocation that was made.
COMP3506/7505, The University of Queensland. 2
Example 1: Given the donations and projects
donations
name total unspent possible
projects
D0 10 10 P0, P1
D1 10 10 P1, P2
D2 5 5 P0
D3 5 5 P2
the program should return the value true, updating the donations and projects by making a
suitable allocation of donations to projects:
donations
name total unspent possible
Projects
D0 10 0 P0, P1
D1 10 0 P1, P2
D2 5 0 P0
D3 5 0 P2
Example 2: Given the donations and projects
the program should return false, and not modify the donations or projects in any way. That is
because there is no possible way to completely fund all of the projects using the conditional
donations available.
Note that not all projects may have the same cost, as in the above examples. Money may be
left over in the donations after a complete allocation is made. In general, there may be many
different compete allocations of funds that are valid.
projects
name cost allocation
P0 10 –
P1 10 –
P2 10 –
projects
name cost allocation
P0 10 (D0, 5), (D2, 5)
P1 10 (D0, 5), (D1, 5)
P2 10 (D1, 5), (D3, 5)
donations
name total unspent possible
projects
D0 10 10 P0, P1, P2
D1 20 20 P0
projects
name cost allocation
P0 10 –
P1 10 –
P2 10 –
COMP3506/7505, The University of Queensland. 3
Task 1: Naïve recursive algorithm implementation [3 marks]:
One way to implement the program that the University of Woolloomooloo wants is to
implement a naïve recursive algorithm that basically tries to allocate a dollar at a time to each
possible project it could be allocated to:
Algorithm canAllocate(donations, projects)
Input: A list of donations that have not been allocated to any projects yet, and a set of
projects that currently have no allocated funds.
Output: Returns false if there is no way to completely fund the projects using the donations,
leaving both the inputs unmodified; otherwise returns true and allocates funding
from the donations to the to projects.
return canAllocateHelper(donations, projects, 0)
Algorithm canAllocateHelper(donations, projects, i)
Input: A list of donations (that may be partially spent), a set of projects that may have
partial (or complete) allocations of funds, and an index 0 <=i <= donatons.size()
Output: Returns false if there is no way to complete the funding of the projects using the
(unspent portion of the) donations from index i onwards, and does not modify the
inputs; or returns true otherwise, completing the allocation of funds to each project.
if all of the projects have been completely allocated then
return true
if index i is at the end of the donations list (i.e. no more donations to allocate)
return false
donation ← donations.get(i)
if there are no funds left in the donation to spend or there are no projects that donation
could be spent on that still need funding then
return canAllocateHelper(donations, projects, i+1)
for each of the projects p that donation could be spent on, and still needs funding
allocate one dollar of donation to p
if canAllocateHelper(donations, projects, i) then
return true
else
deallocate one dollar from donation to p
return false
Implement the naïve recursive algorithm above in the method canAllocate that belongs to
the class a2.NaiveAllocator that is available in in the assignment zip file. (Within the
confines of this recursive approach) do so as efficiently as you can - you are allowed to
choose exactly what parameters you want your helper method to take and so forth as long as
you implement the recursive solution correctly.
You must not change the name or signature of the method canAllocate, or the name or
package of the class to which it belongs. Do not change class a2.Donation or
a2.Project in any way. You should also not write any code that is operating-system
COMP3506/7505, The University of Queensland. 4
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.
You may (and should) use the Java 7 SE API in your implementation, but no other libraries
should be used. (It is not necessary and makes marking hard.)
Any extra classes that you write should be included in the file a2.NaiveAllocator as
private nested classes. Any additional class methods should also be private.
To help you get your solution right, you should write you own JUnit tests in
a2.test.NaiveAllocatorTest (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.
Task 2: Naïve recursive algorithm analysis and justification [4 marks]:
Let n be the number of donations, m the number of projects, x the total number of dollars
worth of donations available, y the total number of dollars required to fund all of the projects.
What is a lower bound on the worst-case time complexity of your recursive implementation
from Task 1 in terms of parameters n, m, x and y?
Express your answers in big-Omega notation, making the bound as tight as possible, and
simplifying your answer as much as possible. Justify your answer. Describe when the worstcase behaviour (w.r.t. time complexity) would occur – give an example.
COMP3506/7505, The University of Queensland. 5
Task 3: Iterative algorithm implementation [8 marks]:
There is another way to implement the program using an iterative approach.
We say that x dollars of funding could be transferred from one project p to another q when x
dollars of donations that have been currently allocated to p may also be spent on project q.
For example for the following donations
donations
name total unspent possible
projects
D0 10 5 P0, P1, P3
D1 10 0 P0, P1
D2 5 0 P0, P2
if the donations (D0, 5), (D1, 10) and (D2, 5) were currently allocated to project P0 then up
to 15 dollars could be transferred from P0 to P1.
Given a set of donations and an incomplete allocation of those donations to projects, we know
that you cannot completely fund the projects using the donations if there does not exist an
integer x>0 and a list of n>0 distinct projects
path = [P0,…,Pn-1]
from the set of projects such that:
1. Project path[n-1] is currently underfunded by at least x dollars
2. x dollars of funding could be allocated from the available donations to project
path[0].
3. for each i=n-2 to 0, x dollars from project path[i] could be transferred to project
path[i+1]
That means that we can find a complete allocation of donations to projects, if one exists, by
repeatedly:
• finding a non-negative integer x and a path of n>0 distinct projects path satisfying
properties (1)-(3) above
• for i=n-2 to 0 transferring x dollars of allocated funds from project path[i] to
path[i+1]
• allocating x dollars from the available donations to project path[0]
until a complete allocation is found. Such a path of projects may be efficiently found using a
graph traversal algorithm like depth-first search or breadth-first search (treating the projects
like vertices and the ability to transfer funds from one project to another like an edge). If at
any time during the process we discover that no such path exists, then we can conclude that
no allocation is possible, de-allocate any allocations that we have tried to make and return
false. The algorithm will terminate because at least one extra dollar is allocated on each
iteration, and the total dollars required to fund all of the projects completely is finite.
COMP3506/7505, The University of Queensland. 6
Example 3: Starting from the following donations and projects,
donations
name total unspent possible
projects
D0 10 10 P0, P1
D1 10 10 P1, P2
D2 5 5 P0
D3 5 5 P2
we could find the solution provided in Example 1, using the iterative approach by:
1. First observing that $10 could be transferred to P0 along path=[P0], yielding
temporary allocation:
donations
name total unspent possible
projects
D0 10 0 P0, P1
D1 10 10 P1, P2
D2 5 5 P0
D3 5 5 P2
2. Then observing that $10 could be transferred to P2 along path=[P2], yielding:
donations
name total unspent possible
projects
D0 10 0 P0, P1
D1 10 0 P1, P2
D2 5 5 P0
D3 5 5 P2
projects
name cost allocation
P0 10 –
P1 10 –
P2 10 –
projects
name cost allocation
P0 10 (D0, 10)
P1 10 –
P2 10 –
projects
name cost allocation
P0 10 (D0, 10)
P1 10 –
P2 10 (D1, 10)
COMP3506/7505, The University of Queensland. 7
3. $5 could be transferred to P1 along path=[P2, P1], giving:
donations
name total unspent possible
projects
D0 10 0 P0, P1
D1 10 0 P1, P2
D2 5 5 P0
D3 5 0 P2
4. $5 could be transferred to P1 along path=[P0, P1], giving us a complete allocation:
donations
name total unspent possible
projects
D0 10 0 P0, P1
D1 10 0 P1, P2
D2 5 0 P0
D3 5 0 P2
projects
name cost allocation
P0 10 (D0, 10)
P1 10 (D1, 5)
P2 10 (D1, 5), (D3, 5)
projects
name cost allocation
P0 10 (D0, 5), (D2, 5)
P1 10 (D1, 5), (D0, 5)
P2 10 (D1, 5), (D3, 5)
COMP3506/7505, The University of Queensland. 8
Example 4: Starting from the following donations and projects,
we can show that there is no possible allocation for Example 2 by observing that:
1. First observing that $10 could be transferred to P0 along path=[P0], yielding
temporary allocation:
2. $10 could be transferred to P1 along path=[P0, P1], yielding temporary allocation:
3. Then we can observe that although P2 is underfunded, there is no path of money from
the unallocated donations to project P2 and so we can deallocate our existing
allocations and return false.
donations
name total unspent possible
projects
D0 10 10 P0, P1, P2
D1 20 20 P0
projects
name cost allocation
P0 10 –
P1 10 –
P2 10 –
donations
name total unspent possible
projects
D0 10 0 P0, P1, P2
D1 20 20 P0
projects
name cost allocation
P0 10 (D0, 10)
P1 10 –
P2 10 –
donations
name total unspent possible
projects
D0 10 0 P0, P1, P2
D1 20 10 P0
projects
name cost allocation
P0 10 (D1, 10)
P1 10 (D0, 10)
P2 10 –
COMP3506/7505, The University of Queensland. 9
Your task is to implement this iterative algorithm for solving the problem as efficiently as you
can in the method canAllocate that belongs to the class a2.IterativeAllocator that is
available in the assignment zip file.
You must not change the name or signature of the method canAllocate, or the name or
package of the class to which it belongs. Do not change class a2.Donation or
a2.Project in any way. You should also not 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.
You may (and should) use the Java 7 SE API in your implementation, but no other libraries
should be used. (It is not necessary and makes marking hard.)
Any extra classes that you write should be included in the file a2.IterativeAllocator as
private nested classes. Any additional class methods should also be private.
To help you get your solution right, you should write you own JUnit tests in
a2.test.IterativeAllocatorTest (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. Our tests will include large tests that will check that your implementation will work
on larger sized problems and will be equipped with timeouts.
Task 4: COMP7505 ONLY: Iterative algorithm analysis and justification [3 marks]
What is the worst-case time complexity of your iterative implementation in Task 3?
Express your answers in big-Oh notation, making the bound as tight as possible, and
simplifying your answer as much as possible. Justify your answer. You should express your
answer in terms of suitably chosen measures of the input size of the program, and you must
explain what those parameters are.
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.
Submission: Submit you source code files NaiveAllocator.java and
IterativeAllocator.java as well as your written answers in report.pdf
electronically using Blackboard according to the exact instructions on the Blackboard
website:
https://learn.uq.edu.au/
Answers to Tasks 2 (and 4 for COMP7505 students) 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. 10
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 and efficiency questions if we cannot read and understand your
solution to check your analysis or evaluate the efficiency of your solution.
Task 1: [3 marks]
Given that the solution does implement the recursive algorithm, and does not violate any
restrictions (using forbidden libraries etc), marks will be allocated based on the outcome of
running test cases:
• All of our tests pass 3 marks
• At least 66% of our tests pass 2 marks
• At least 33% of our tests pass 1 mark
• 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 or doesn’t implement the recursive algorithm given will
receive zero marks.
Task 2: [4 marks]
• The algorithm analysis and justifications (including example) are correct and complete.
4 marks
• The algorithm analysis and justifications (including example) contain only very minor
errors or omissions. 3 marks
• The algorithm analysis and justifications (including example) are reasonable but contain
some errors or omissions. 2 marks
• The algorithm analysis and justifications (including example) contain many errors or
omissions or a major error or omission. 1 mark
• Work with little or no academic merit 0 marks
Note: A mark of 0 will be given for this part if no reasonable attempt was made to complete
Task 1 or the solution to Task 1 is difficult to read and comprehend, or incorrect.
COMP3506/7505, The University of Queensland. 11
Task 3: [8 marks]
Given that the solution does efficiently implement the iterative algorithm, and does not
violate any restrictions (using forbidden libraries etc), marks will be allocated based on the
outcome of running test cases. Our tests will include large tests that will check that your
implementation is efficient: they will be equipped with timeouts.
• All of our tests pass 8 marks
• At least 85% of our tests pass 7 marks
• At least 75% of our tests pass 6 marks
• At least 65% of our tests pass 5 mark
• At least 50% of our tests pass 4 marks
• At least 35% of our tests pass 3 mark
• At least 25% of our tests pass 2 mark
• At least 15% of our tests pass 1 mark
• 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 or doesn’t efficiently implement iterative algorithm given
will receive zero marks.
Task 4: COMP7505 ONLY [3 marks]
• The algorithm analysis and justifications are correct and complete. 3 marks
• The algorithm analysis and justifications are reasonable but contain some errors or
omissions. 2 marks
• The algorithm analysis and justifications contain many errors or omissions or a major
error or omission. 1 mark
• Work with little or no academic merit 0 marks
Note: A mark of 0 will be given for this part if no reasonable attempt was made to complete
Task 3 or the solution to Task 3 is difficult to read and comprehend, or incorrect.
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.
