COMP4500/7500-无代写-Assignment 2
时间:2024-10-08
Advanced Algorithms and Data Structures
School of Electrical Engineering and Computer Science
The University of Queensland, Semester 2, 2024
Assignment 2
Due at 3pm, Friday 18th of October 2024.
This assignment is worth 20% (COMP4500) or 15% (COMP7500) of your final grade.
This assignment is to be attempted individually. It aims to test your understanding of dynamic program-
ming. Please read this entire handout before attempting any of the questions.
Submission. Answers to each of the written (not programming) questions (i.e. Q1(b), Q1(d), Q1(e))
should be clearly labeled and included in a pdf file called A2.pdf.
You need to submit (i) your written answers in A2.pdf, as well as (ii) your source code files
Recursive.java and Dynamic.java electronically using Blackboard according to the exact instructions on
the Blackboard website: https://learn.uq.edu.au/
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 - incorrect submissions will
receive 0 marks.
Submitted work should be neat, legible and simple to understand – you may be penalised for work that is
untidy or difficult to read and comprehend.
For the programming part, you will be penalised for submitting files that are not compatible with the
assignment requirements. In particular, code that is submitted with compilation errors, or is not compatible
with the supplied testing framework will receive 0 marks.
Late submission. See the course profile for details.
A penalty of 10% of the maximum possible mark will be deducted per 24 hours from the time submission
is due for up to 7 days. After 7 days, you will receive a mark of 0.
If there are medical or exceptional circumstances, then you may apply for an extension capped at a maximum
of 7 days from the original deadline. Extensions must be requested via my.UQ (https://my.uq.edu.au/).
School Policy on Student Misconduct. You are required to read and understand the School Statement
on Misconduct, available at the School’s website at:
https://eecs.uq.edu.au/current-students/student-guidelines/student-conduct This is an indi-
vidual assignment. If you are found guilty of misconduct (plagiarism or collusion) then penalties will
be applied.
COMP4500/7500 Assignment 2 (September 30, 2024) 2
Question 1 (100 marks total)
You are in charge of running a small business – a microbrewery out of your garage – for k consecutive
days. You have a schedule, represented by an array work of k non-negative integers (indexed from 0) for
the amount of work you have committed to complete on each of the k days that you are in charge of the
business, e.g. the amount of work you have committed to complete on the first day, day 0, is work.get(0),
for the second day, day 1, is work.get(1), etc.
Being a small business, you have only two workers available – your two best friends – worker w0 and
worker w1. For i ∈ {0, 1}, worker wi has a maximum number of days that they can work in a row,
wi.maxShift, where wi.maxShift ≥ 1; a minimum number of days that they need to take off between work
shifts, wi.minBreak, where wi.minBreak ≥ 1; and for each day d ∈ {0, 1, . . . , k − 1}, an amount of work,
wi.capacity(d), where wi.capacity(d) ≥ 0, that they could complete on day d, and a salary cost wi.cost(d),
where wi.cost(d) ≥ 0 of working on day d.
Before the first day that you are in charge of the small business, day 0, neither worker has worked any
days (they have never been on a shift). After the last day you are in charge of the business, day k − 1, the
business will close and neither worker will work for any more days.
A roster for the k days that you are in charge of the small business is a list of length k, where for each
day d ∈ {0, 1, . . . , k − 1}, roster.get(d) is the set of workers that are scheduled to work on day d, where
roster.get(d) ⊆ {w0, w1}. Such a roster is valid as long as, for each i ∈ {0, 1}, worker wi does not work
more than wi.maxShift days in a row, and every break between worker wi’s shifts is greater than or equal
to wi.minBreak days (i.e. if wi is rostered to work on some day d, but they are not rostered to work on
day d+ 1, then they also cannot be rostered to work on any day d′ ∈ {d+ 1, . . . , d+ wi.minBreak}).
For a given roster r and a day d ∈ {0, 1, . . . , k−1}, the maximum amount of work that can be completed on
day d, denoted capacity(r, d) is either: 0 if r.get(d) = {}; w0.capacity(d) if r.get(d) = {w0}; w1.capacity(d)
if r.get(d) = {w1}; and w0.capacity(d) +w1.capacity(d) if r.get(d) = {w0, w1}. As such, the scheduled work
that cannot be completed on that day is max(0, work.get(d) − capacity(r, d)). The cost of a roster r for a
day d ∈ {0, 1, . . . , k − 1} is defined to be the sum of the scheduled work that cannot be completed on day d
plus the salary costs of the workers who are scheduled to work on day d.
The total cost of a roster r is then the sum of the cost of the roster for each of the k days.
Given workers w0 and w1, and a work schedule work for k days, your task is to find a valid roster for
the k days you are in charge of the small business that has the minimum total cost.
A valid roster for the k days that you are in charge of the small business that has the minimum total cost
is said to be optimal.
Example: As an example, consider the scenario where you are in charge of the business for k = 5 days,
and the and the amount of work that you have committed to for each day is:
work = [15, 5, 12, 17, 7]
and the two workers that you have available are:
w0 = (maxShift=2, minBreak=1, capacity=[10, 4, 5, 0, 8], cost=[1, 2, 2, 1, 1])
w1 = (maxShift=1, minBreak=3, capacity=[6, 8, 3, 2, 3], cost=[0, 1, 1, 1, 2])
A valid roster for the k = 5 days that you are in charge of the business that has the minimum total cost is:
roster = [{w0, w1}, {}, {w0}, {}, {w0}]
COMP4500/7500 Assignment 2 (September 30, 2024) 3
In the roster, both workers are scheduled to work on day 0; neither worker is scheduled to work on day 1;
only worker w0 is scheduled to work on day 2; neither worker is scheduled to work on day 3; and only worker
w0 is scheduled to work on day 4. The total cost of this roster is:
(max(0, 15− (10 + 6)) + (1 + 0) + (i.e. day 0 cost)
(max(0, 5− (0 + 0))) + (0 + 0) + (i.e. day 1 cost)
(max(0, 12− (5 + 0))) + (2 + 0) + (i.e. day 2 cost)
(max(0, 17− (0 + 0))) + (0 + 0) + (i.e. day 3 cost)
(max(0, 7− (8 + 0))) + (1 + 0) + (i.e. day 4 cost)
= 1 + 5 + 9 + 17 + 1
= 33
Many other valid rosters are possible, however, in this scenario, none of them have a smaller cost. For
example, the following valid roster:
roster = [{w0, w1}, {w0}, {}, {w0}, {w0, w1}]
has a cost of:
(max(0, 15− (10 + 6)) + (1 + 0) + (i.e. day 0 cost)
(max(0, 5− (4 + 0))) + (2 + 0) + (i.e. day 1 cost)
(max(0, 12− (0 + 0))) + (0 + 0) + (i.e. day 2 cost)
(max(0, 17− (0 + 0))) + (1 + 0) + (i.e. day 3 cost)
(max(0, 7− (8 + 3))) + (1 + 2) + (i.e. day 4 cost)
= 1 + 3 + 12 + 18 + 3
= 37
[Note: In the zip file that accompanies this handout you will find a method getCost in the DynamicTest
class in the assignment2.test package, which, for testing purposes, is used to check that a roster is valid with
respect to given inputs, and also to calculate its cost. Except for testing purposes, you should not be using
methods getCost yourself, but it may help you to refer to it if you are having trouble understanding the
problem.]
a. (20 marks) Your first task is to identify the optimal substructure of the problem. You must implement
the public static method optimalRecursive from the Recursive class in the assignment2 package that
is available in the zip file that accompanies this handout, to provide a naive recursive algorithm to
determine the total cost of an optimal valid roster for the k days that you are in charge of the small
business.
The recursive solution does NOT need to return a valid roster itself that results in the minimum
total cost – it just needs to return the total cost of such an optimal (valid) roster. Efficiency is not
a great concern for this part (the inefficiency will be expected to come from recomputing solutions to
overlapping subproblems), so focus on an elegant solution that identifies the optimal substructure of
the problem. (You must not provide a dynamic programming solution to this question.)
b. (15 marks) It is expected that your recursive algorithm for part (a) will not be polynomial-time in
the worst case. For the case where there are k days for which you will be running the small business
give an asymptotic lower bound on the worst-case time complexity of your recursive algorithm
in terms of parameter k. Make your bound as tight as possible. (We would like you to be able
to show that your recursive algorithm, in the worst case, has a time complexity that is worse than
polynomial-time.)
As part of your answer you need to provide a lower-bound recurrence (in terms of parameter k)
that describes the worst-case time complexity of your recursive algorithm; you need to justify your
COMP4500/7500 Assignment 2 (September 30, 2024) 4
recurrence, explaining why it appropriately describes a lower bound on the worst-case time complexity
of your algorithm; and you need to solve your recurrence (showing your working) to derive your answer
to this question.
[Make your answer as concise as possible – it should be no more than a page using minimum 11pt
font. Longer answers will not be marked.]
c. (30 marks) Develop an efficient bottom-up dynamic programming solution to the problem (not mem-
oised) by implementing the public static method optimalDynamic in the Dynamic class from the as-
signment2 package that accompanies this handout.
Your dynamic programming solution should run in polynomial time if terms of k, the number of days
you are in charge of the small business, and it should be as efficient as possible.
The dynamic solution does NOT need to return a a (valid) roster itself that results in the minimum
total cost – it just needs to return the total cost of such an optimal (valid) roster.
d. (10 marks) Provide an asymptotic upper bound on the worst-case time complexity of your
dynamic programming solution for part (c) in terms of the parameter k (the number of days you are
in charge of the small business). Make your bounds as tight as possible and justify your solution.
[Make your answer as concise as possible – it should be no more than half a page using minimum 11pt
font. Longer answers will not be marked.]
e. (5 marks) Provide an asymptotic upper bound on the worst-case space complexity of your
dynamic programming solution for part (c) in terms of the parameter k (the number of days you are
in charge of the small business). Make your bounds as tight as possible and justify your solution.
[Make your answer as concise as possible – it should be no more than half a page using minimum 11pt
font. Longer answers will not be marked.]
f. (20 marks) Extend your bottom-up dynamic programming solution from part (c) to calculate a (valid)
roster with the least cost by implementing the public static method optimalSolutionDynamic in the
Dynamic class from the assignment2 package.
Like method optimalDynamic, your implementation of this method should run in polynomial time (in
terms of k), and it should be as efficient as possible. It must be a bottom-up dynamic programming
(not memoised) solution.
Practicalities
Do not change the class name of the Recursive or Dynamic classes or the package to which those files
belong. You may not change the signatures of the methods that you have to implement in any way or
alter their specifications. (That means that you cannot change the method name, parameter types, return
types or exceptions thrown by the those methods.) Do not modify any of the other classes or interfaces or
enumerated types defined in package assignment2.
Your implementation should be in Java 22. Do not use imports for external packages other than those in
java.util.*. (Note that IntelliJ may offer the option of importing an external package to resolve an issue;
please avoid taking this option because it will often add an erroneous import that you will not need. Such
imports lead to the compilation failing in the environment in which your compiler will be assessed because
that environment may not include the external libraries. Please check you are not importing external
libraries before submitted.)
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 file should be written using ASCII characters
only.
COMP4500/7500 Assignment 2 (September 30, 2024) 5
You may not write and submit any additional classes. Your solution to Q1(a) should be self-contained in the
Recursive class. Similarly your solution to parts Q1(c) and Q1(f) should be self-contained in the Dynamic
class. Both of these classes will be tested in isolation and should not depend upon each other.
The zip file for the assignment also some JUnit test classes to help you get started with testing your code.
The junit test classes as provided in the package assignment2.test are not intended to be an exhaustive
test for your code. Part of your task will be to expand on these tests to ensure that your code behaves as
required.
Your implementation will be tested by executing our own set of JUnit test cases. Code that is submitted
with compilation errors, or is not compatible with the supplied testing framework will receive 0 marks. A
Java 22 compiler will be used to compile and test the code. The Recursive class will be tested in isolation
from the Dynamic class.
Implementations that do not satisfy the assignment requirements will receive 0 marks even if they pass some
of the test cases (e.g. if the solution given to Q1(c) is not an efficient bottom-up dynamic programming
solution, then it will receive 0 marks.)
You may lose marks for poorly structured, poorly documented or hard to comprehend code, or code that is
not compatible with the assignment requirements. Line length should be less than or equal to 100 characters
so that it can be printed – please use spaces to indent your code instead of tabs to ensure compatibility with
different machines. Don’t leave print statements in your submitted code.
Evaluation Criteria
Question 1
• Question 1 (a) (20 marks)
Given that your implementation satisfies the requirements of the question (i.e. the method must be
implemented using a naive recursive programming solution that identifies the optimal substructure of
the problem), your implementation will be evaluated for correctness by executing our own set of JUnit
test cases.
20 : All of our tests pass
16 : at least 80% of our tests pass
12 : at least 60% of our tests pass
8 : at least 40% of our tests pass
4 : at least 20% of our tests pass
0 : less than 20% of our test pass or work with little or no academic merit
Note: Code that is submitted with compilation errors, or is not compatible with the supplied testing
framework will receive 0 marks. A Java 22 compiler will be used to compile and test the code.
Implementations that do not satisfy the assignment requirements will receive 0 marks even if they pass
some of the test cases.
The Recursive class will be tested in isolation from the Dynamic class.
• Question 1 (b) (15 marks)
For this part of the question, the analysis should be no more than one page using minimum 11pt font.
Longer solutions will receive 0 marks. Also, if a plausible, neat, legible and simple to understand
COMP4500/7500 Assignment 2 (September 30, 2024) 6
solution to Q1(a) has not been given, this question will receive 0 marks. Otherwise the following
marking criteria applies.
15 : A correct asymptotic lower bound on the worst-case time complexity the recursive algorithm
from Q1(a) is given in terms of the parameters specified in the question. The lower bound, which
is exponential, is reasonably tight for the algorithm at hand. The time-complexity given is clearly
justified by giving, justifying and solving a correct (lower bound) recurrence derived from your
algorithm. Any assumptions made in the analysis are reasonable and clearly stated. Asymptotic
notation is used correctly and the asymptotic time complexity given has been simplified to remove
lower order terms and unnecessary constant factors.
11 : A good attempt has been made to give an asymptotic lower bound on the worst-case time
complexity of the recursive algorithm from Q1(a) in terms of the parameters specified in the
question. The lower bound is exponential. The answer and justification contains at most one or
two minor mistakes or omissions. The time-complexity given is mostly clearly justified by giving,
justifying and solving a (lower bound) recurrence derived from your algorithm. Any assumptions
made in the analysis are mostly reasonable and clearly stated.
7 : A reasonable attempt has been made to give a tight asymptotic lower bound on the worst-case
time complexity of the recursive algorithm from Q1(a) in terms of the parameters specified in the
question, and to justify it with respect to a recurrence derived from the algorithm, however the
analysis or justification contains minor mistakes or omissions or lacks clarity.
3 : An attempt has been made to both give an asymptotic lower bound on the worst-case time
complexity of the recursive algorithm from Q1(a) in terms of the parameters specified in the
question, and to justify it in terms of a recurrence derived from your algorithm, however it
contains either a major mistake or many mistakes, gives an unreasonably loose lower bound, or is
not clearly justified by giving, justifying and solving a correct (lower bound) recurrence derived
from your algorithm.
0 : Work with little or no academic merit.
• Question 1 (c) (30 marks)
Given that your implementation satisfies the requirements of the question (i.e. it is a efficient bottom-
up dynamic programming (not memoised) solution that runs in polynomial time in terms of parameter
k), your implementation will be evaluated for correctness and efficiency by executing our own set of
JUnit test cases.
30 : All of our tests pass
24 : at least 80% of our tests pass
18 : at least 60% of our tests pass
12 : at least 40% of our tests pass
6 : at least 20% of our tests pass
0 : less than 20% of our test pass or work with little or no academic merit
Note: Code that is submitted with compilation errors, or is not compatible with the supplied testing
framework will receive 0 marks. A Java 22 compiler will be used to compile and test the code.
Implementations that do not satisfy the assignment requirements will receive 0 marks even if they pass
some of the test cases.
The Dynamic class will be tested in isolation from the Recursive class.
COMP4500/7500 Assignment 2 (September 30, 2024) 7
• Question 1 (d) (10 marks)
For this part of the question, the analysis should be no more than 1/2 of a page using minimum 11pt
font. Longer solutions will receive 0 marks. Also, if a plausible, neat, legible and simple to understand
solution to Q1(c) has not been given, this question will receive 0 marks. Otherwise the following
marking criteria applies.
10 : A correct asymptotic upper bound on the worst-case time complexity of the algorithm from
Q1(c) is given in terms of the parameters specified in the question. The upper bound, which is
polynomial in the parameters specified in the question, is as tight as reasonably possible for the
algorithm at hand. The time-complexity given is clearly justified with respect to the algorithm.
Any assumptions made in the analysis are reasonable and clearly stated. Asymptotic notation
is used correctly and the asymptotic time complexity given has been simplified to remove lower
order terms and unnecessary constant factors.
7 : A good attempt has been made to give an asymptotic upper bound on the worst-case time
complexity the algorithm from Q1(c) in terms of the parameters specified in the question. The
upper bound is polynomial in terms of those parameters. The answer and justification contains at
most one or two minor mistakes or omissions. The time-complexity given is mostly clearly justified
with respect to the algorithm. Any assumptions made in the analysis are mostly reasonable and
clearly stated.
5 : A reasonable attempt has been made to give a tight asymptotic upper bound on the worst-case
time complexity of the algorithm from Q1(c) in terms of the parameters specified in the question,
and to justify it, however the analysis or justification contains minor mistakes or omissions or
lacks clarity.
2 : An attempt has been made to give an asymptotic upper bound on the worst-case time complexity
of the algorithm from Q1(c) in terms of the parameters specified in the question, and justify it,
however it contains either a major mistake or many mistakes, gives an unreasonably loose upper
bound, or is not clearly justified.
0 : Work with little or no academic merit.
• Question 1 (e) (5 marks)
For this part of the question, the analysis should be no more than 1/2 of a page using minimum 11pt
font. Longer solutions will receive 0 marks. Also, if a plausible, neat, legible and simple to understand
solution to Q1(c) has not been given, this question will receive 0 marks. Otherwise the following
marking criteria applies.
5 : A correct asymptotic upper bound on the worst-case space complexity of the algorithm from
Q1(c) is given in terms of the parameters specified in the question. The upper bound, which is
polynomial in the parameters specified in the question, is as tight as reasonably possible for the
algorithm at hand. The space-complexity given is clearly justified with respect to the algorithm.
Any assumptions made in the analysis are reasonable and clearly stated. Asymptotic notation
is used correctly and the asymptotic space complexity given has been simplified to remove lower
order terms and unnecessary constant factors.
4 : A good attempt has been made to give an asymptotic upper bound on the worst-case space
complexity the algorithm from Q1(c) in terms of the parameters specified in the question. The
upper bound is polynomial in terms of those parameters. The answer and justification may
contain at most one or two minor mistakes or omissions. The space-complexity given is mostly
clearly justified with respect to the algorithm. Any assumptions made in the analysis are mostly
reasonable and clearly stated.
COMP4500/7500 Assignment 2 (September 30, 2024) 8
2 : A reasonable attempt has been made to give a tight asymptotic upper bound on the worst-case
space complexity of the algorithm from Q1(c) in terms of the parameters specified in the question,
and to justify it, however the analysis or justification contains minor mistakes or omissions or
lacks clarity.
1 : An attempt has been made to give an asymptotic upper bound on the worst-case space com-
plexity of the algorithm from Q1(c) in terms of the parameters specified in the question, and to
justify it, however it contains either a major mistake or many mistakes, gives an unreasonably
loose upper bound, or is not clearly justified.
0 : Work with little or no academic merit.
• Question 1 (f) (20 marks)
Given that your implementation satisfies the requirements of the question (i.e. it is an efficient bottom-
up dynamic programming (not memoised) solution that runs in polynomial time in terms of k), your
implementation will be evaluated for correctness and efficiency by executing our own set of JUnit test
cases.
20 : All of our tests pass
16 : at least 80% of our tests pass
12 : at least 60% of our tests pass
8 : at least 40% of our tests pass
4 : at least 20% of our tests pass
0 : less than 20% of our test pass or work with little or no academic merit
Note: Code that is submitted with compilation errors, or is not compatible with the supplied testing
framework will receive 0 marks. A Java 22 compiler will be used to compile and test the code.
Implementations that do not satisfy the assignment requirements will receive 0 marks even if they pass
some of the test cases.
The Dynamic class will be tested in isolation from the Recursive class.