COMP4500/7500
Advanced Algorithms and Data Structures
School of Electrical Engineering and Computer Science The University of Queensland, Semester 2, 2024
Assignment 2
Copyright By PowCoder代写 加微信 powcoder
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 dayd+1,thentheyalsocannotberosteredtoworkonanydayd′ ∈{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 dayd∈{0,1,…,k−1}isdefinedtobethesumofthescheduledworkthatcannotbecompleted ondayd 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:
has a cost of:
(max(0,15−(10+6))+(1+0)+ (max(0,5−(0+0)))+(0+0)+ (max(0,12−(5+0)))+(2+0)+ (max(0,17−(0+0)))+(0+0)+ (max(0,7−(8+0)))+(1+0)+
= 1+5+9+17+1
(i.e. day 0 cost) (i.e. day 1 cost) (i.e. day 2 cost) (i.e. day 3 cost) (i.e. day 4 cost)
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}]
(max(0,15−(10+6))+(1+0)+ (max(0,5−(4+0)))+(2+0)+ (max(0,12−(0+0)))+(0+0)+ (max(0,17−(0+0)))+(1+0)+ (max(0,7−(8+3)))+(1+2)+
= 1+3+12+18+3
(i.e. day 0 cost) (i.e. day 1 cost) (i.e. day 2 cost) (i.e. day 3 cost) (i.e. day 4 cost)
[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
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com