COMP3027
report代写 | Algorithm | oop代写 | 作业assignment – 这道题目是利用Algorithm进行的编程代写任务, 涵盖了report/Algorithm/oop等方面, 这个项目是assignment代写的代写题目
Algorithms 3027/3927 assignment 1 The University of Sydney
2022 Semester 1 School of Computer Science
This assignment is for COMP3027 only. Grattis! Youve been hired to assist the packaging operations at Ikea. Your first task is to evaluate a bid from a box manufacturer. Roughly speaking, the ideal box manufacturer is one whose boxes can fit as many Ikea products as possible. In particular, you are given a listPofnproductsp 1 ,… , pnwhere product pihas lengthlength(pi) and widthwidth(pi), and a listBofmboxesb 1 ,… , bmwhere boxbjhas length length(bj) and widthwidth(bj). We say that productpifitsinto boxbjiflength(pi)length(bj) and width(pi)width(bj). (Unfortunately, the packing machine is unable to rotate products due to damage, so no rotations are allowed.) Thetotal fitis the total number of product-box pairs (pi, bj) such thatpi fits inbj. Note that this is different from the total number of products that can fit inat least onebox. The goal is to compute the total fit.
Figure 1:p 1 andp 2 fit in boxb 1 ;p 2 fits in boxb 2 so the total fit is 3.
Note that there may be multiple products and/or boxes that share the same length and/or width.
Task 1: Keep It Simple, Single-Dimensional [5 points]
We start with the simple case where products and boxes are one-dimensional, i.e. they only have a length. (Believe it or not, thinking about this is actually useful for the other parts of the assignment.) Here, we are given a listP ofnproductsp 1 ,… , pnwhere productpihas lengthlength(pi), and a list Bofmboxesb 1 ,… , bmwhere boxbjhas lengthlength(bj). We say that productpifitsinto boxbjif length(pi)length(bj). Thetotal fitis the total number of product-box pairs (pi, bj) such thatpifits inbj. Your task is to design an Algorithm that computes the total fit inO(NlogN) time whereN=m+n and implement your algorithm on Ed. (You are not required to submit a description of the algorithm and proof of correctness and time complexity, but you should also practice describing your algorithm in plain English and proving correctness and time complexity as it will help with Task 2.)
Task 2: Two-Dimensional [95 points]
We can think of the products and boxes as points in two-dimensional space with length as thex-coordinate and width being they-coordinate. Thus, it is natural to divide the input using a horizontal or vertical line, i.e. divide the products and boxes according to their width or length, respectively. Before deciding on exactly what the line should be, it is useful to design the combine step.
(a)Combine stepIn this subtask, we will design the combine step subroutine assuming that the
divide step divides products and boxes into those whose length are at mostDand those that are
at leastD, for someD. Formally, the inputs to the combine step are:
- 4 listsPL, PR, BL, BR. The listPLconsist of productspiwithlength(pi)DandPRconsist of productspiwithlength(pi)D. Ditto forBLandBR. Moreover, each list is sorted in ascending order of width,
- FL, the total fit of productsPLwith boxesBL, i.e. the number of pairs (pi, bj) wherepiis in PLandbjis inBLandpifits inbj.
- FR, the total fit of productsPRwith boxesBR, i.e. the number of pairs (pi, bj) wherepiis in PRandbjis inBRandpifits inbj.
The output of the combine step is the total fit of products in bothPLandPRwith all boxes in
BLandBR, i.e. the number of pairs (pi, bj) wherepiis inPLorPR,bjis inBLorBR, andpifits
inbj. Your task is to design anO(N) time algorithm for the combine step, whereNis the total
number of products and boxes, i.e.N=|PL|+|PR|+|BL|+|BR|. (Note: You may choose to solve
a different version of the combine step. If you choose to do so, make sure you clearly define what
the inputs and outputs of your combine step are.)
(i) Description of how your algorithm works in plain English.
(ii) Prove that your algorithm is correct.
(iii) Prove an upper bound on the time complexity of your algorithm.
(iv) Implement your algorithm on Ed
(b) Use the combine step algorithm above to construct a divide-and-conquer algorithm for the problem.
For full marks, your algorithm should take timeO(NlogN) whereN=m+n, the total number
of products and boxes.
(i) Description of how your algorithm works in plain English. Make sure you describe
- your pre-processing step (if needed)
- the problem your recursive algorithm is solving, i.e. its input and output.
- your divide step (subproblems, base cases)
- your delegate step
- how you use the combine step subroutine (ii) Prove that your algorithm is correct (iii) Prove an upper bound on the time complexity of your algorithm (iv) Implement your algorithm on Ed
Guidelines
To make it easier for you to write and for us to mark, you can simply assume the following without further explanation/proof when describing/analyzing your algorithm.
- Computing the min or max of an unsorted list ofnvalues takesO(n) time. You can simply write LetAbe the max of the input list. Do not tell us the for l oop to do this.
- Sorting a list ofnvalues takesO(nlogn) time. You can simply write Sort list L in ascending order of blah and assume it takesO(nlogn) time without specifying what sort you are using. Please do not re-write or re-prove mergesort or any other sorting algorithm.
- Check whether a productpifits in a boxbjinO(1) time. You can simply write Ifpifits inbjthen blah instead of writing iflength(pi)length(bj) andwidth(pi)width(bj) then blah.
Submission details
- Submission deadline is Wednesday 23 March, at 23:59. Late submissions without special consideration will be subject to the penalties specified in the first lecture (5% per day).Submis- sions later than Friday 25 March, 23:59 will not be accepted.
- 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 (1- pages of a4 for 3027 and 2-3 for 3927).
- 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 of the precise algorithms, examples, proofs, writing, or code.
- To facilitate anonymous grading, please do not write your name on your submission.