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 section 5.3 of the course profile for details. Assessment submissions received after the due time (or any approved extended deadline) will be subject to a 100% late penalty. A one-hour grace period will be applied to the due time after which time the 100% late penalty will be imposed. This grace period is designed to deal with issues that might arise during submission (e.g. delays with Blackboard or Turnitin) and should not be considered a shift of the due time. Please keep a record of your submission time.

If there are medical or exceptional circumstances, then you may apply for an extension capped at a maximum of 14 days from the original deadline. Extensions must be requested via my.UQ (https://my.uq.edu.au/). If you have been granted an extension, then the 100% late submission penalty will apply to submissions made after the due date of the approved extension. The one-hour grace period will also apply to the extended deadline.

on Misconduct, available at the School’s website at: http://www.itee.uq.edu.au/itee-student-misconduct-including-plagiarism This is an individual assignment. If you are found guilty of misconduct (plagiarism or collusion) then penalties will be applied.

Question 1 (100 marks total)

The only way to leave a remote island is by ferry, and the island has only one ferry terminal, which is attended by one full-time attendant. Each passenger who arrives at the ferry terminal must be checked in by the attendant in order to be able to catch their boat. The attendant can only check in one customer at a time.

For the purpose of this question, time units will be measured as non-negative integers (i.e. integers that are greater than or equal to zero).

Each passenger has an arrival time, the time that the passenger arrives at the ferry terminal to check in, a departure time, the time that the passenger’s ferry departs the terminal, a check-in time, the (exact) time that it takes for the attendant to check-in the passenger. The check-in time for a passenger must be greater than or equal to one time unit, and the arrival time of a passenger plus their check-in time must be no later than their departure time. Passengers also have the propensity to become frustrated depending on whether or not their ferry ticket is cancelled, and, if their ferry ticket is not cancelled, how long they have

to wait after arriving at the ferry terminal to commence their check-in. Frustration is measured in terms of non-negative integers. If δ < δ0 , the frustration of a passenger p at having to wait δ time units after their arrival to commence check-in, is guaranteed to be no more than their frustration at having to wait δ0 time units after their arrival to commence check-in, i.e. shorter waits can be no more frustrating than longer waits. (Note that some passengers may be particularly cantankerous, and will be frustrated even if they are able to commence check-in immediately upon their arrival.) The frustration of a passenger p at being cancelled must be strictly greater than their frustration of having to wait (any 0 or more units of time) to commence check-in.

The attendant has, in advance, a list of n passengers, p0, p1,...pn−1, where n ≥ 0. The list of passengers is ordered in non-decreasing order of their arrival time at the ferry terminal. (More than one passenger can arrive at the same time.)

The attendant needs to plan ahead in order to minimise the total frustration of the n passengers in the list. For each passenger pi, for 0  i  n − 1, the attendant needs to determine whether or not to cancel their ticket, and, if pi’s ticket is not cancelled, then they need to be assigned a time  ti to commence check-in,

pi in the list of passengers needs to have either had their ticket cancelled, or they must have completed checked-in (according to the plan) before pi can commence check-in.

The attendant needs to make a plan that satisfies these constraints (is valid) and minimises the total frustration of all the passengers in the list, i.e. the sum of the frustration of each passenger pi, for 0 <= i<n, given whether or not pi will have their ticket cancelled, and if they have not had their ticket cancelled, when they are scheduled to commence check-in.

Your task is to find a (valid) plan for the attendant that minimises the total frustration of th passengers.

p0 : (arrival: 0, departure=10, checkInTime=2, cancelFrustration=3, waitFrustration=[0, 0, 0, 0, 1, 1, 1, 1, 1])

p1 : (arrival: 0, departure=3, checkInTime=1, cancelFrustration=15, waitFrustration=[0, 1, 4])

p2 : (arrival: 0, departure=8, checkInTime=4, cancelFrustration=7, waitFrustration=[1, 2, 2, 5, 6])

p3 : (arrival: 4, departure=9, checkInTime=2, cancelFrustration=10, waitFrustration=[0, 6, 6, 6])

p4 : (arrival: 12, departure=14, checkInTime=1, cancelFrustration=10, waitFrustration=[0, 1])

p5 : (arrival: 13, departure=14, checkInTime=1, cancelFrustration=5, waitFrustration=[2])

where, for brevity, we represent the wait-time frustration of each passenger p as an array p.waitF rustration (indexed from 0), such that for 0 < δ < p.departure −

p.arrival − p.checkInT ime, p.waitF rustration[δ] represents the frustration of passenger p having to wait δ time units after their arrival to commence check-in.

A (valid) plan that minimises the total frustration of the passengers is one that cancels p0, sets t1 = 0, cancels p2, sets t3 = 4, t4 = 12 and t5 = 13 , which can be represented compactly as the array

plan = [null, 0, null, 4, 12, 13]

(indexed from 0), that for each i such that 0  i<n, plan[i] is null if pi is cancelled, and ti otherwise. The

p0.cancelF rustration +

p1.waitF rustration[t1 − p1.arrival] +

p2.cancelF rustration +

p3.waitF rustration[t3 − p3.arrival] +

p4.waitF rustration[t4 −p4.arrival] +

p5.waitF rustration[t5  − p5.arrival]

= 3+0+7+0+0+2

= 12

plan = [0, 2, 3, 7, 12, 13]

[Note: In the zip file that accompanies this handout you will find the Passenger class in the assignment2 package. In the assignment2.test package you will also find a method checkPlan in the DynamicTest class, which, for testing purposes, is used to check that a plan is valid with respect to the algorithm inputs (a list of passengers), and a method totalFrustration, which given a valid plan for a list of passengers, calculates the total frustration of the passengers given the plan. Except for testing purposes, you should not be using methods checkPlan or totalFrustration 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 minimum total frustration of the passengers.

The recursive solution does NOT need to return a (valid) plan itself that results in the minimum total passenger frustration – it just needs to return the total passenger frustration of such an optimal (valid) plan. 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 will not be polynomial-time in the worst case. For the case where there are n passengers, and the earliest arrival time of any passenger in the list is x (take x = 0 if there are no passengers in the list), and the latest departure time of any passenger in the list is y (take y = 0 if there are no passengers in the list), give an asymptotic lower bound on the worst-case time complexity of your recursive algorithm in terms of parameters n, x and y, or a relevant subset of those parameters. 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 parameters n, x and y, or a relevant subset of those) that describes the worst-case time complexity of your recursive algorithm; you need to justify your 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 (in terms of n (the number of passengers in the list), x (the earliest arrival time of any passenger in the list) and y (the latest departure time of any passenger in the list)), and it should be as efficient as possible.

The dynamic solution does NOT need to return a a (valid) plan itself that results in the minimum total passenger frustration – it just needs to return the total passenger frustration of such an optimal (valid) plan.

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 parameters n, the number of passengers in the list, x, the earliest arrival time of any passenger in the list, and y, the latest departure time of any passenger in the list, or an appropriate subset of those parameters. 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 parameters n, the number of passengers in the list, x, the earliest arrival time of any passenger in the list, and y, the latest departure time of any passenger in the list, or an appropriate subset of those parameters. 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) plan that minimises the total frustration of the passengers, 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 n, x and y), and it should be as efficient as possible. It must be a bottom-up dynamic programming (not memoised) solution.

Practicalities

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.

You are encouraged to use Java 8 SE API classes, but no third party libraries should be used. (It is not necessary, and makes marking hard.) Don’t write any code that is operating-system specific (e.g. by hardcoding 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.

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 programming implementations 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 8 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 di↵erent machines. Don’t leave print statements in your submitted code.

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 8 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 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 should be exponential, should be reasonably tight for the algorithm at hand. The time complexity given should be 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 should be used correctly and the asymptotic time complexity given has been simplified to remove lower order terms and unnecessary constant factors.

11 : A very good attempt has been made to give an 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 should be exponential. The answer and justification may contain at most one or two minor mistakes or omissions. The time-complexity given should be 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 may contain minor mistakes or omissions or lack 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 n, x and y), 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 8 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.

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 should be polynomial in the parameters specified in the question, should be as tight as reasonably possible for the algorithm at hand. The time-complexity given should be clearly justified with respect to the algorithm. Any assumptions made in the analysis are reasonable and clearly stated. Asymptotic notation should be used correctly and the asymptotic time complexity given has been simplified to remove lower order terms and unnecessary constant factors.

7 : A very 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 should be polynomial in terms of those parameters. The answer and justification may contain at most one or two minor mistakes or omissions. The time-complexity given should be 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 may contain minor mistakes or omissions or lack 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)

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 should be polynomial in the parameters specified in the question, should be as tight as reasonably possible for the algorithm at hand. The space-complexity given should be clearly justified with respect to the algorithm. Any assumptions made in the analysis are reasonable and clearly stated. Asymptotic notation should be used correctly and the asymptotic space complexity given has been simplified to remove lower order terms and unnecessary constant factors.

4 : A very 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 should be 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 should be mostly clearly justified with respect to the algorithm. Any assumptions made in the analysis are mostly reasonable and clearly stated.

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 may contain minor mistakes or omissions or lack 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 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 n, x and y), 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 8 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.