School: School of Electrical Engineering and Computer Science, The University of Queensland Semester: 2, 2024 Due Date: 3pm, Friday 18th of October 2024
- This assignment is worth 20% (COMP4500) or 15% (COMP7500) of the final grade.
- It is to be attempted individually and aims to test understanding of dynamic programming.
- Written Answers: Answers to written questions (Q1(b), Q1(d), Q1(e)) should be in a pdf file called
A2.pdf. - Source Code:
Recursive.javaandDynamic.javashould be submitted electronically via Blackboard according to the instructions on https://learn.uq.edu.au/. - Multiple submissions are allowed before the deadline, but only the last one will be saved and marked.
- Submitted work should be neat, legible, and simple to understand. Incorrect submissions will receive 0 marks.
- A penalty of 10% of the maximum possible mark will be deducted per 24 hours for up to 7 days. After 7 days, a mark of 0 will be given.
- Medical or exceptional circumstances require an extension request via https://my.uq.edu.au/ with a maximum of 7 days from the original deadline.
- Read and understand the School Statement on Misconduct available at https://eecs.uq.edu.au/current-students/student-guidelines/student-conduct. Plagiarism or collusion will result in penalties.
- You are in charge of a small microbrewery business for
kconsecutive days. You have a work schedule represented by an arrayworkofknon-negative integers. - There are two workers
w0andw1with specific working constraints such as maximum number of consecutive days they can work (maxShift), minimum number of days off between shifts (minBreak), their capacity to complete work on each day (capacity), and salary cost for working on each day (cost). - A roster for the
kdays is a list where each element indicates the set of workers scheduled to work on that day. A roster is valid if it satisfies the workers' constraints. - The goal is to find a valid roster for the
kdays with the minimum total cost.
- Consider
k = 5days,work = [15,5,12,17,7],w0 = (maxShift = 2, minBreak = 1, capacity = [10,4,5,0,8], cost = [1,2,2,1,1]), andw1 = (maxShift = 1, minBreak = 3, capacity = [6,8,3,2,3], cost = [0,1,1,1,2]). - An optimal roster is
roster = [{"w0", "w1"},{},{"w0"},{},{"w0"}]with a total cost of 33.
- (a) Optimal Substructure - Recursive Solution (20 marks)
- Implement the
public static method optimalRecursivein theRecursiveclass to provide a naive recursive algorithm to determine the total cost of an optimal valid roster. The method should not return the roster itself but only the total cost.
- Implement the
- (b) Time Complexity of Recursive Algorithm (15 marks)
- Give an asymptotic lower bound on the worst-case time complexity of the recursive algorithm in terms of
k. Provide a lower-bound recurrence, justify it, and solve it.
- Give an asymptotic lower bound on the worst-case time complexity of the recursive algorithm in terms of
- (c) Dynamic Programming Solution (30 marks)
- Implement the
public static method optimalDynamicin theDynamicclass to develop an efficient bottom-up dynamic programming solution (not memoised) to find the total cost of an optimal valid roster.
- Implement the
- (d) Time Complexity of Dynamic Programming Solution (10 marks)
- Provide an asymptotic upper bound on the worst-case time complexity of the dynamic programming solution in terms of
k.
- Provide an asymptotic upper bound on the worst-case time complexity of the dynamic programming solution in terms of
- (e) Space Complexity of Dynamic Programming Solution (5 marks)
- Provide an asymptotic upper bound on the worst-case space complexity of the dynamic programming solution in terms of
k.
- Provide an asymptotic upper bound on the worst-case space complexity of the dynamic programming solution in terms of
- (f) Extended Dynamic Programming Solution (20 marks)
- Implement the
public static method optimalSolutionDynamicin theDynamicclass to extend the bottom-up dynamic programming solution to calculate a valid roster with the least cost.
- Implement the