Algorithms 3027/3927 Assignment 1 The University of Sydney
2022 Semester 1 School of Computer Science
This assignment is for COMP3027 only.
Grattis! You’ve 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 list P of n products p1, . . . , pn where product
pi has length length(pi) and width width(pi), and a list B of m boxes b1, . . . , bm where box bj has length
length(bj) and width width(bj). We say that product pi fits into box bj if length(pi) ≤ length(bj)
and width(pi) ≤ width(bj). (Unfortunately, the packing machine is unable to rotate products due to
damage from the Great Flood of 2022, so no rotations are allowed.) The total fit is the total number
of product-box pairs (pi, bj) such that pi fits in bj . Note that this is different from the total number of
products that can fit in at least one box. The goal is to compute the total fit.
Figure 1: p1 and p2 fit in box b1; p2 fits in box b2 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 list P of n products p1, . . . , pn where product pi has length length(pi), and a list
B of m boxes b1, . . . , bm where box bj has length length(bj). We say that product pi fits into box bj if
length(pi) ≤ length(bj). The total fit is the total number of product-box pairs (pi, bj) such that pi fits
in bj .
Your task is to design an algorithm that computes the total fit in O(N logN) time where N = 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 the x-coordinate
and width being the y-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 step In this subtask, we will design the combine step subroutine assuming that the
divide step divides products and boxes into those whose length are at most D and those that are
more than D, for some D. Formally, the inputs to the combine step are:
1
• 4 lists PL, PR, BL, BR. The list PL consist of products pi with length(pi) ≤ D and PR consist
of products pi with length(pi) > D. Ditto for BL and BR. Moreover, each list is sorted in
ascending order of width,
• FL, the total fit of products PL with boxes BL, i.e. the number of pairs (pi, bj) where pi is in
PL and bj is in BL and pi fits in bj .
• FR, the total fit of products PR with boxes BR, i.e. the number of pairs (pi, bj) where pi is in
PR and bj is in BR and pi fits in bj .
The output of the combine step is the total fit of products in both PL and PR with all boxes in
BL and BR, i.e. the number of pairs (pi, bj) where pi is in PL or PR, bj is in BL or BR, and pi fits
in bj . Your task is to design an O(N) time algorithm for the combine step, where N is 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 time O(N logN) where N = 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 of n values takes O(n) time. You can simply write
“Let A be the max of the input list”. Do not tell us the for loop to do this.
• Sorting a list of n values takes O(n log n) time. You can simply write “Sort list L in ascending order
of blah” and assume it takes O(n log n) 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 product pi fits in a box bj in O(1) time. You can simply write “If pi fits in bj then
blah” instead of writing “if length(pi) ≤ length(bj) and width(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-2
pages of a4 for 3027 and 2-3 for 3927).
2
• The implementations should be done in Ed, and submitted via Ed.
• Your report will be subject to automatic and manual plagiarism detection systems. Remember, it’s
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.
3