# COMP4500编程辅导、Java语言程序辅导

- 首页 >> Algorithm 算法 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.

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.