TITLE
report | 代做Algorithm | assignment代写 – 这道题目算法代写任务, 是有一定代表意义的Algorithm等代写方向, 这个项目是assignment代写的代写题目
Algorithms 3027/3927 assignment 2
This assignment is for both COMP3027 and COMP3927 students. COMP3027 students should do Tasks 1 and 2 while COMP3927 students should do Tasks 1 and 3.
Now that we have secured a box manufacturer, its time to get those packages to the customers. The customers are located in annngridGwithn2. Serving customer location (i, j) gives us profit G(i, j). We will be using the convention that (i, j) is the location at columniand rowj, and (0,0) is the top-left and (n 1 , n1) is the bottom-right. The goods will be delivered using a drone. The drone starts from the depot located at (0,0). The drone can move downwards along the grid (e.g. from (i, j) to (i, j+ 1)), rightwards (e.g. from (i, j) to (i+ 1, j), and diagonally (e.g. from (i, j) to (i+ 1, j+ 1)). The drone needs to end up at the depot located at (n 1 , n1). Moreover, sharp turns (a downwards move followed immediately by a rightwards move or a rightwards move followed immediately by a downwards move) are undesirable as it causes the drone to sway, damaging the packages inside. More precisely, we are given annngrid with non-negative integersG(i, j) for 0in1 and 0 jn1 such thatG(0,0) =G(n 1 , n1) = 0 (these are depots, not customers). Our goal is to determine the maximum total profit that can be achieved by a delivery path starting from (0,0) and consisting of a sequence of downwards, rightwards, and diagonal moves and ending at (n 1 , n1) with few sharp turns. Note that we are only interested in the profit of the optimal path, not the actual path. For instance, supposeGis the following grid. Then, a possible delivery path is (0,0)(1,0) (1,1)(2,2)(3,2)(3,3). This path has two sharp turns and a total profit of 4 + 100 + 3 + 10 = 117.
0 4 6 8
3 100 7 9
8 3 3 10
2 1 4 0
Figure 1: The gridG
0 4 6 8
3 100 7 9
8 3 3 10
2 1 4 0
Figure 2: A delivery path with two sharp turns
Task 1: No sharp turns [15 points]
We begin by considering the case when no sharp turns are allowed. The goal is to find the maximum profit we can achieve using a delivery path with no sharp turns.
(a) You start by brainstorming out loud with your trusty companion Rubber Duck.
You: Lets start with some basic facts. Surely the optimal path must visit the most profitable
location and achieve a profit of at least maxi,jG(i, j), right?
Rubber Duck:Hmm... Are you sure?
Your first task is to give a gridGalong with profitG(i, j) for each location on the grid such that it
is not possible to visit the most profitable location with no sharp turns.You need to submitGin
a form that can be quickly verified visually by either submitting a picture (such as the figure above)
or ASCII art. For example, a submission that describes a 5 5 grid with the profitsG(i, j)written
out in a list will not be accepted.
(b) Implement on Ed a dynamic programming Algorithm that returns the maximum profit achievable
using a delivery path with no sharp turns. Your algorithm should have time complexityO(n^2 ). [
points]
Task 2 (3027 only): Some sharp turns are allowed [85 points]
In this task, we are also given as input a non-negative numberSand our goal is to find the maximum profit we can achieve using a delivery path with at mostSsharp turns. Your task is to design and analyze a dynamic programming algorithm for this problem. For full marks, your algorithm should have time complexity at mostO(n^2 S). (Note: If you are only able to solve Task 1, you can instead describe and analyze an algorithm for Task 1 with time complexityO(n^2 )for partial marks.)
(a) Define the subproblems needed by your algorithm.
What we expect to see: Definition of OPT(... ), and its parameters
(b) Define the recurrence.
What we expect to see: a recurrence that relates each subproblem to smaller subproblems. We
just want to see a clear description of the recurrence here. The justification for the recurrence goes
into (e).
(c) Define the base cases.
What we expect to see: A description of the base cases and the values that OPT(..) takes on these
base cases.
(d) Describe how the maximum profit is obtained fromOP T(..).
What we expect to see: A description of how to obtain the optimal value to the original problem
using the optimal values of the subproblems.
(e) Justify your recurrence and base cases, and that your answer to part (d) correctly returns the
optimal value.
What we expect to see: The sufficiency of the base cases, i.e. the recurrence will always end up at a
base case, the correctness of the recurrence and the values for the base cases, and that you correctly
obtained the optimal revenue fromOP T(..).
(f) Prove the time complexity of your algorithm.
What we expect to see: An analysis of the running time required to compute all theOP T(..)values
and to obtain the maximum revenue fromOP T(..)
(g) Implement your algorithm on Ed. [10 points]
Task 3 (3927 only): Minimise number of sharp turns [85 points]
In this task, we are also given as input a non-negative numberP. Our goal is to determine if it is possible to achieve a profit of at leastP, and if so to find the minimum number of sharp turns needed to achieve a profit at leastP. Your task is to design and analyze a dynamic programming algorithm for this problem. For full marks, your algorithm should have time complexity at mostO(n^3 ).(Note: If you are only able to solve Task 1, you can instead describe and analyze an algorithm for Task 1 with time complexityO(n^2 ) for partial marks.)
(a) Define the subproblems needed by your algorithm.
What we expect to see: Definition of OPT(... ), and its parameters
(b) Define the recurrence.
What we expect to see: a recurrence that relates each subproblem to smaller subproblems. We
just want to see a clear description of the recurrence here. The justification for the recurrence goes
into (e).
(c) Define the base cases.
What we expect to see: A description of the base cases and the values that OPT(..) takes on these
base cases.
(d) Describe how the minimum number of sharp turns of a path that achieves at leastT profit is
obtained fromOP T(..).
What we expect to see: A description of how to obtain the optimal value to the original problem
using the optimal values of the subproblems.
(e) Justify the correctness of your recurrence and base cases, and that your answer to part (d) correctly
returns the optimal value.
What we expect to see: The sufficiency of the base cases, i.e. the recurrence will always end up at a
base case, the correctness of the recurrence and the values for the base cases, and that you correctly
obtained the optimal revenue fromOP T(..).
(f) Prove the time complexity of your algorithm.
What we expect to see: An analysis of the running time required to compute all theOP T(..)values
and to obtain the maximum revenue fromOP T(..)
(g) Implement your algorithm on Ed. [10 points]
Submission details
- Submission deadline is Wednesday 6 April, at 23:59.Late submissions without special con- sideration will be subject to the penalties specified in the first lecture (5% per day).Submissions later than Friday 8 April, 23:59 will not be accepted.
- Familiarize yourself with following Ed posts and resources:
- General Assignment Guidelineshttps://edstem.org/au/courses/7844/discussion/
- How to Approach Problemshttps://edstem.org/au/courses/7844/resources?download= 13488
- Submit your answers as a single document to Gradescope. Your work must be typed (no images of text, although you can use diagrams if you think it helps.) Please try to be reasonably concise (about 2-3 pages of A4)
- The implementations should be done in Ed, and submitted via Ed.
- Your report will be subject to automatic and manual plagiarism detection systems. Remember, its acceptable to discuss high level ideas with your peers, but you should not share the detail of your work, such as parts as the precise algorithms, examples, proofs, writing, or code.
- To facilitate anonymous grading, please do not write your name on your submission.
Exemplar for Knapsack
The following exemplar is designed to help you understand the requirements of the assignment. You should still write your submission in your own words and not plagiarize the exemplar.
(a) Define the subproblems needed by your algorithm.
Consider the items in some arbitrary order. Define OPT(i, w) to be the optimal solution to the
knapsack problem consisting of the firstiitems and weight limitwfor 0inand 0wW.
Wheni= 0, this corresponds to a knapsack problem with no items.
(b) Define the recurrence and base cases.
OPT(i, w) =
{
OPT(i 1 , w) ifwi> w,
max{vi+ OPT(i 1 , wwi),OPT(i 1 , w)} otherwise
(c) Define the base cases
The base cases are wheni= 0. In this case, OPT(0, w) = 0 for all 0wW.
(d) Describe how to obtain the most value achieved by any feasible subset of items from the subproblems.
The most value achieved is in the subproblem OPT(n, W).
(e) Justify your recurrence, base cases, as well as how you obtain the optimal value to the original
problem fromOP T(..).
The base cases are sufficient as each OPT(i, w) depends on some OPT(i 1 , w). Thus, the recurrence
will always end up at OPT(0, w) for somew. We have OPT(0, w) = 0 since the most value that
can be achieved with no items is 0.
We now justify the recurrence. LetS(i, w) be the optimal solution for the firstiitems with weight
limitw. The recurrence for OPT(i, w) is correct because:
- ifwi> w, thenS(i, w) cannot contain itemiand so is a subset of the firsti1 items with weight at mostw, soS(i, w) =S(i 1 , w) and OPT(i, w) = OPT(i 1 , w)
- ifwiw, then either itemiis inS(i, w) or not:
- if itemiis inS(i, w), then the remaining items ofS(i, w) is a subset of the firsti 1 items with weight at mostwwisoS(i, w) ={i}S(i 1 , wwi) and so OPT(i, w) = vi+ OPT(i 1 , wwi).
- else,S(i, w) is a subset of the firsti1 items with weight at mostw, soS(i, w) =S(i 1 , w) and OPT(i, w) = OPT(i 1 , w).
Finally, the optimal value for the original problem is OPT(n, W) as by definition of OPT, this is
the most value that can be achieved by a subset of allnitems with a weight limit ofW.
(f) Prove the time complexity of your algorithm.
The base cases take timeO(W) as there areW+ 1 of them and setting them to 0 takes constant
time. For the recursive cases, there areO(nW) iterations and each iteration takesO(1) time since
it only requires a constant number of comparisons, arithmetic operations and array lookups. Thus,
the recursive cases takes timeO(nW). Returning the optimal value takesO(1) time for an array
lookup. Thus, the total time isO(W) +O(nW) +O(1) =O(nW).