COMP4500/7500 Advanced Algorithms and Data Structures Assignment 2

Question 1 (100 marks total)

You are in charge of managing a venue for k consecutive days from day 0 to day k - 1 (inclusive), where k > 1.

There are n different configurations, c0 , cl , . . . cn一l, that the venue can be in, where n > 1. The venue must be in exactly one of the n different configurations at any one time, and is in configuration c0  on day 0. The cost of having the venue in a configuration c for day d is given by c.cost(d), where c.cost(d) > 0. The cost of a configuration can be different on different days (e.g. if d  d\ then c.cost(d) does not necessarily equal c.cost(d\ )), and different configurations may have different costs.

Each configuration c has a set-up time, c.setupTime(), and a tear-down time, c.teardownTime(), such that c.setupTime() > 1 and c.teardownTime() > 1.  It is possible to change the venue from its current config- uration cold  to any different configuration cnew, however the reconfiguration takes cold .teardownTime() + cnew .setupTime() whole consecutive days to complete. For the first cold .teardownTime() of those days the venue is still in configuration cold, and for the last cnew .setupTime() of those days, the venue is in the new configuration cnew . Once a reconfiguration is started it must be completed without interruption, and it must be completed before day k (e.g. the last day of any reconfiguration must be less than or equal to day k - 1). Additionally, the venue cannot be used to host any bookings for the duration of the reconfiguration. Other than this, there are no limits on the number of times the venue can be reconfigured.  (The configuration of

the venue can only be changed by reconfiguring it in the way described above.)

In order to earn money, the venue can host events.

There are m event booking  requests  b0 , bl , . . . bm一l, where m > 0.  Each booking request, b, has an event start day, b.start(), and an event end day, b.end(), where 0 < b.start() < b.end() < k - 1.  As the venue manager, you can choose to host any number of the events that you have booking requests for as long as: if you host a booking request b, then you must host it for all of the (whole) days from b.start() to b.end(), inclusive (i.e. you must host the whole event); and you can only host one event at a time (e.g. there cannot be day where you are hosting more than one event); you cannot host an event while the venue is being reconfigured.

The payment received for hosting the event booking b depends on the configuration of the venue.   The payment that would be received for hosting event booking b in a configuration c is given by b.payment(c) where b.payment(c) > 0.

In summary there are three different kinds of activities  that can be taking place at the venue on any one of the k days you are in charge of it:  either it can be idle  in its current configuration, being reconfigured from one configuration to another one, or it can be hosting an event (for a booking request) in its current configuration.

A schedule for the venue, assigns each of the k days that you are in charge of the venue to an activity.  In a schedule, the activities must be assigned in such a way as to respect the constraints described above (e.g. the venue is in configuration c0 on day 0; once a reconfiguration is commenced it must be completed without interruption before day k; if the event from a booking request is hosted, then it must be hosted for all of the whole days specified in the booking request, etc.).

The profit of a schedule is the sum of the payments received by hosting the events in the schedule, minus the configuration costs for each of the k days.

Your task is to find a schedule with the maximum profit.  (That is, you want to work out how to manage the venue so that you can get the best possible profit.)

As an example, consider the scenario where k = 11, there are n = 2 configurations:

c0:  (setup=1, teardown=1, cost=[1, 0, 2, 1, 0, 0, 1, 1, 1, 5, 0])

c1:  (setup=2, teardown=1, cost=[0, 6, 3, 1, 1, 1, 1, 1, 2, 0, 8])

and m = 4 booking requests:

b0:  (start=0, end=1, payment= (c0 →f 4), (c1 →f 3) )

b1:  (start=0, end=0, payment= (c0 →f 2), (c1 →f 7) )

b2:  (start=3, end=3, payment= (c0 →f 2), (c1 →f 5) )

b3:  (start=4, end=6, payment= (c0 →f 3), (c1 →f 12))

A schedule with the maximum profit is:

day 0: HOSTING b1 in configuration c0

day 1: RECONFIGURING c0 to c1

day 2: RECONFIGURING c0 to c1

day 3: RECONFIGURING c0 to c1

day 4: HOSTING b3 in configuration c1

day 5: HOSTING b3 in configuration c1

day 6: HOSTING b3 in configuration c1

day 7: IDLE in configuration c1

day 8: IDLE in configuration c1

day 9: RECONFIGURING c1 to c0

day 10: RECONFIGURING c1 to c0

in which:  (i) event booking b1 is hosted in c0 from day 0 to day 0; (ii) the venue is reconfigured from c0 to c1 from day 1 to 3; (iii) the event booking b3 is hosted in c1 from day 4 to day 6; (iv) the venue is idle in c1 for day 7; (v) the venue is idle in c1 for day 8; and finally (vi) the venue is reconfigured from c1 to c0 from day 9 to day 10.

In this schedule the payments received from hosting the events in the schedule is

b1.payment(c0) + b3.payment(c1) = 2 + 12 = 14

and the configuration costs for each of the k days are

(1 + 0) + (3 + 1 + 1 + 1 + 1 + 1 + 2 + 0) + (0) = 11

since the venue is in c0 on days 0 and 1 (inclusive); in c1 from days 2 to 9 (inclusive); and in c0 again on day 10. This means that the schedule has a profit of 14 - 11 = 3, which is the maximum profit of any schedule.

Note that there are many other possible schedules, but none of them have a profit which is greater than 3. For example, another possible schedule is:

day 0: HOSTING b0 in configuration c0

day 1: HOSTING b0 in configuration c0

day 2: IDLE in configuration c0

day 3: HOSTING b2 in configuration c0

day 4: HOSTING b3 in configuration c0

day 5: HOSTING b3 in configuration c0

day 6: HOSTING b3 in configuration c0

day 7: IDLE in configuration c0

day 8: IDLE in configuration c0

day 9: IDLE in configuration c0

day 10: IDLE in configuration c0

however the payments received from hosting the events in this schedule is

b0.payment(c0) + b2.payment(c0) + b3.payment(c0) = 4 + 2 + 3 = 9 and the configuration costs for each of the k days are (since the venue is always in c0):

1 + 0 + 2 + 1 + 0 + 0 + 1 + 1 + 1 + 5 + 0 = 12

and so this schedule has a profit of 9 - 12 = -3, which is less than the maximum possible profit of 3.

[Note:  In the zip file that accompanies this handout you will find the Activity class in the assignment2 package.  If you need clarification of what an activity is, please refer to this class.  In the assignment2.test package you will also find a method checkSchedule in the DynamicTest class, which, for testing purposes, is used to check that a schedule is valid with respect to the algorithm inputs, and calculates the profit of the schedule.  Except for testing purposes, you should not be using method checkSchedule 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 optimalProfitRecursive 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 maximum profit of any schedule.

The recursive solution does NOT need to return a schedule that has the maximum profit – it just needs to return the maximum profit. 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 the number of days you are managing the venue for is k, the number of configurations is n, and the number of booking requests is m, give an asymptotic lower bound on the worst-case time complexity of your recursive algorithm in terms of parameters k , n and m, 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 k , n and m, 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 optimalProfitDynamic in the Dynamic class from the assignment2 package that accompanies this handout.

Your dynamic programming solution should run in polynomial time (in terms of k , n and m), and it should be as efficient as possible.

The dynamic solution does NOT need to return a schedule that would result in the maximum profit – it just needs to return the maximum profit.

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 k (the number of days), n (the number of configurations) and m (the number of booking requests), 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 k (the number of days), n (the number of configurations) and m (the number of booking requests), 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 schedule with the maximum profit, by implementing the public static method optimalScheduleDynamic in the Dynamic class from the assignment2 package.

Like method optimalProfitDynamic, your implementation of this method should run in polynomial time (in terms of k , n and m), 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.

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 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 k , n and m), 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 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)

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 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 k , n and m), your implementation will be evaluated for correctness and efficiency by executing our own set of junit test cases.

20  : All of our tests pass