COMP4500/7500 Assignment 2 (September 27, 2021) 2
Question 1 (100 marks total)
You are in charge of managing bookings for car ferries.
There are m car ferries that are numbered from 0 to m? 1, in order of their departure time. For simplicity,
no two ferries depart at the same time, and so the numbering is unique. For j in the range 0 to m? 1, the
jth ferry to depart is fj whole meters in length. The length of each ferry is non-negative (i.e. it is greater
than or equal to zero).
There are n different cars, c0, c1, . . . cn?1, where n > 0. Each car has a length (in whole meters), as well
as a ferry that they have booked a ticket for. The length of each car must be greater than zero, and the
number of the ferry that they are booked for must be greater than or equal to 0 and less than m ? 1 (i.e.
no cars can be booked for the last ferry to depart, ferry number m? 1).
The cars are ordered in non-decreasing order of the ferry that each car has a ticket for. That is, for any i
from 0 to n? 2, the number of the ferry that ci has a ticket booked for is less than or equal to the number
of the ferry that car ci+1 has a ticket booked for.
Each of the first m ? 1 car ferries may have zero or more car bookings (and the last car ferry can have no
car bookings). In fact, it is possible for one or more of the ferries to be over-booked. A ferry is over-booked
if the sum of the lengths of the cars which are booked for the ferry exceeds the length of the ferry.
Your job, as the manager of the ferry bookings, is to review the bookings and determine a ferry allocation
for each car, where each car is either able to be allocated to:
(i) the ferry that they have a ticket for (their chosen ferry)
(ii) the first ferry that departs after the ferry that they have a ticket for (i.e. if a car has a ticket booked
for ferry j, then they can be allocated to the next ferry, ferry j + 1.)
(iii) no ferry at all – i.e. they can have their ticket canceled.
Such an allocation of cars to ferries is valid if and only if:
There is exactly one allocation for each car, and each car is either allocated to (i) the ferry that they
have a ticket for, or (ii) the first ferry that departs after the ferry that they have a ticket booked for,
or (iii) for no ferry at all.
The sum of the lengths of the cars allocated to each ferry does not exceed (i.e. is less than or equal
to) the length of the ferry.
Note that even though the last ferry cannot have any bookings made for it, cars can still be allocated to it,
i.e. a car with a booking for ferry m? 2 may be able to be allocated to ferry m? 1.
Each car has as a cost associated with being rescheduled to the next ferry, and a cost associated with having
their ferry ticket canceled. The rescheduling cost, as well as the cancellation cost must be greater than zero,
and the cancellation cost must be greater than the cost of being rescheduled to the next ferry.
The cost of an allocation for a car is either: (i) equal to 0, if the car is allocated to the ferry that they have
a booking for; or (ii) the rescheduling cost for that car, if the car is rescheduled to the next ferry; or (iii)
the cancellation cost for that car, if the car is not allocated to a ferry at all.
Your job is to find a valid allocation of cars to ferries, that minimizes the total allocation cost,
i.e. the sum of the allocation cost for each car.
COMP4500/7500 Assignment 2 (September 27, 2021) 3
As an example, consider the scenario where there are m = 5 ferries with lengths f0 = 4, f1 = 11, f2 = 10,
f3 = 0, f4 = 20 and n = 7 cars
c0 = (2, 0, 1, 2),
c1 = (9, 0, 1, 5),
c2 = (3, 0, 1, 3),
c3 = (5, 1, 2, 6),
c4 = (2, 1, 3, 6),
c5 = (15, 2, 2, 10),
c6 = (5, 3, 1, 2)
where each car above is described by their length, followed by the number of the ferry that they have a
booking for, their rescheduling cost, and their cancellation cost. For example car c6 has a length of 5, a
booking for ferry number 3, a rescheduling cost of 1, and a cancellation cost of 2.
Not all allocations of cars to ferries are valid, for example, allocation
c0 to ferry 0,
c1 to ferry 1,
c2 to ferry 0,
c3 to ferry 2,
c4 to ferry 1,
c5 to no ferry
c6 to ferry 4
is not valid because the sum of the lengths of the cars allocated to ferry 0 is 2 + 3 = 5, which is greater than
4, the length of the ferry. The following allocation is also not valid :
c0 to ferry 1,
c1 to no ferry ,
c2 to ferry 0,
c3 to ferry 1,
c4 to ferry 1,
c5 to ferry 4
c6 to ferry 4
The reason that it is not valid, is that it assigns car c5 to ferry 4, which is neither the ferry that c5 is booked
for (ferry 2) nor the next ferry (ferry 3).
There are many possible valid allocations of cars to ferries. For example, allocation
c0 to ferry 1,
c1 to no ferry ,
c2 to ferry 0,
c3 to ferry 1,
c4 to ferry 1,
c5 to no ferry
c6 to ferry 4
is valid, and has total allocation cost 1 + 5 + 0 + 0 + 0 + 10 + 1 = 17. It is not, however, a valid allocation
with the minimum possible total allocation cost.
COMP4500/7500 Assignment 2 (September 27, 2021) 4
A valid allocation with the minimum cost is
c0 to no ferry
c1 to ferry 1,
c2 to ferry 0,
c3 to ferry 2,
c4 to ferry 1,
c5 to no ferry
c6 to ferry 4
it has a total allocation cost of 2 + 1 + 0 + 2 + 0 + 10 + 1 = 16.
a. (20 marks) Your first task is to identify the optimal substructure of the problem. You must implement
the public static method optimalCostRecursive 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 allocation cost of any valid allocation of cars to ferries.
The recursive solution does NOT need to find a valid allocation that would result in the minimum cost
– it just needs to determine the minimum total allocation cost of any valid allocation. Efficiency is not
at all a concern for this part, 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 the number of ferries is m, the number of cars is n, and the maximum length of
any of the m ferries is C, give an asymptotic lower bound on the worst-case time complexity of your
recursive algorithm in terms of parameters m, n and C, or a relevant subset of those parameters. Make
your bound as tight as possible.
As part of your answer you need to provide a lower-bound recurrence (in terms of parameters m, n
and C 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 optimalCostDynamic in the Dynamic class from the
assignment2 package that accompanies this handout.
Your dynamic programming solution should run in polynomial time (in terms of m, n and C), and it
should be as efficient as possible.
The dynamic solution does NOT need to find a valid allocation that would result in the minimum cost
– it just needs to determine the minimum total allocation cost of any valid allocation.
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 m (the number of ferries) and n (the
number of cars) and C (the maximum length of any of the m ferries), 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.]
COMP4500/7500 Assignment 2 (September 27, 2021) 5
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 m (the number of ferries) and n (the
number of cars) and C (the maximum length of any of the m ferries), 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
allocation of cars to ferries that has the least possible cost, by implementing the public static method
optimalSolutionDynamic in the Dynamic class from the assignment2 package.
Like method optimalCostDynamic, your implementation of this method should run in polynomial time
(in terms of m, n and C), 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 many 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.
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 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.
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 junit4 test classes to help you get started with testing your code.
The JUnit4 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 compatability
with different machines. Don’t leave print statements in your submitted code.
COMP4500/7500 Assignment 2 (September 27, 2021) 6
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 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 parameters m and n and C. The lower bound, which should
be exponential, should be as tight as reasonably possible 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 correct asymptotic lower bound on the worst-case time complexity the recursive algorithm
from Q1(a) is given in terms of parameters m and n and C. The lower bound should be expo-
nential. The time-complexity given should be mostly clearly justified by giving, justifying and
solving a correct (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 parameters m and n and C,
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.
COMP4500/7500 Assignment 2 (September 27, 2021) 7
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 parameters m and n and C, 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 m, n and
C), 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.
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 parameters m, n and C. The upper bound, which should be polynomial
in m, n and C, 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 correct asymptotic upper bound on the worst-case time complexity the algorithm from Q1(c)
is given in terms of parameters m, n and C. The upper bound should be polynomial in m, n and
C. 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 parameters m, n and C, and to justify
it, however the analysis or justification may contain minor mistakes or omissions or lack clarity.
COMP4500/7500 Assignment 2 (September 27, 2021) 8
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 parameters m, n and C, 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 parameters m, n and C. The upper bound, which should be polynomial
in m, n and C, 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 correct asymptotic upper bound on the worst-case space complexity the algorithm from Q1(c)
is given in terms of parameters m, n and C. The upper bound should be polynomial in m, n and
C. 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 parameters m, n and C, 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 parameters m, n and C, 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 m, n and
C), 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.
COMP4500/7500 Assignment 2 (September 27, 2021) 9
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.