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.
欢迎咨询51作业君