Algorithms 3027/3927 Assignment 4 The University of Sydney
2022 Semester 1 School of Computer Science
Task 1 (COMP3027 only): A1 with rotations [30 marks]
Good news! The packing machine has now been fixed and can actually rotate products to fit into boxes.
We now need to re-evaluate bids from box manufacturers. 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, 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 rotationally fits into box bj if at least one of the following conditions hold:
length(pi) ? length(bj) and width(pi) ? width(bj), or
width(pi) ? length(bj) and length(pi) ? width(bj), or
The total rotational fit is the total number of product-box pairs (pi, bj) such that pi rotationally fits in
bj . The goal is to compute the total rotational fit. We call this the Rotational Fit Problem.
Figure 1: p1 and p2 rotationally fit in boxes b1 and b2 so the total rotational fit is 4. Note that p1 only
rotationally fits in b2, it does not non-rotationally fit in b2.
Note that there may be multiple products/boxes that share the same length and/or width.
In this task, we will reduce this problem to that of the problem in A1, which we now call the Non-
Rotational Fit Problem. Recall that in the Non-Rotational Fit Problem, you are also given a list of
products and a list of boxes, each with lengths and widths. We say that product pi non-rotationally fits
into box bj if length(pi) ? length(bj) and width(pi) ? width(bj). The total non-rotational fit is the
total number of product-box pairs (pi, bj) such that pi non-rotationally fits in bj . The goal is to compute
the total non-rotational fit.
The goal in this task is to design an algorithm that takes as input an instance I of the Rotational Fit
Problem and output an instance J of the Non-Rotational Fit Problem such that the total rotational fit
of I is exactly equal to the total non-rotational fit of J .
(a) You: “Looking at the example above, it seems like a product rotationally fits into a box if and only
if either the height or width of the box is at least as large as both dimensions of the product.”
Rubber Duck: “Aha, so maybe the new instance J should have the same set of products as the
original instance I, but with the following set of boxes: for every box bj of I, create a new box
b0j with length(b0j) = width(b0j) = max(length(bj), width(bj)). Then, assuming what you say is
true, a product pi rotationally fits in box bj if and only if product pi non-rotationally fits in box
b0j . Thus, the rotational fit of I is exactly equal to the non-rotational fit of J .”
1
You: “Nice! Ok, so all we need to do is to see if the following statement is true: given a prod-
uct p and box b, p rotationally fits in b if and only if length(p) ? max(length(b), width(b)) and
width(p) ? max(length(b), width(b)).”
Your task is to provide a counter-example to the above reduction.1 In particular, you need to
give a product p and box b such that length(p) ? max(length(b), width(b)) and width(p) ?
max(length(b), width(b)), but p does not rotationally fit in b. (Observe that p and b forms an
instance I of the Rotational Fit Problem such that the instance J produced by the above reduction
does not satisfy the property that the rotational fit of I is equal to the non-rotational fit of J , and
hence is a counterexample to the reduction.) [5 marks]
(i) State the lengths and widths of p and b.
(ii) Show that length(p) ? max(length(b), width(b)) and width(p) ? max(length(b), width(b)).
(iii) Show that p does not rotationally fit in b.
(b) Your task is to implement on Ed a reduction from the Rotational Fit Problem to the Non-
Rotational Fit Problem. In particular, design an algorithm that takes as input an instance I
of the Rotational Fit Problem and outputs an instance J of the Non-Rotational Fit
Problem such that the total rotational fit of I is exactly equal to the total non-rotational fit of J .
For full marks, your algorithm should run in linear time, i.e. O(n+m) time. [25 marks]
Task 2 (COMP3927 only): 3D A1 with rotations [30 marks]
In this problem, each product pi and box bj also has a height height(pi) and height(bj), respectively.
Product pi rotationally fits in box bj if there exists a rotation of pi such that it fits in bj . Note that for 3d
objects, there are 3! = 6 possible rotations. Thus, pi rotationally fits in bj if one of the following holds:
The total rotational fit is the total number of product-box pairs (pi, bj) such that pi fits in bj . The goal
is to compute the total rotational fit. We call this the 3D Rotational Fit Problem.
In this task, we will reduce this problem to that of the problem in A1, which we now call the
3D Non-Rotational Fit Problem. Recall that in the Non-Rotational Fit Problem, you are also given a
list of products and a list of boxes, each with lengths, widths and heights. We say that product pi
non-rotationally fits into box bj if length(pi) ? length(bj), width(pi) ? width(bj) and height(pi) ?
height(bj). The total non-rotational fit is the total number of product-box pairs (pi, bj) such that pi
non-rotationally fits in bj . The goal is to compute the total non-rotational fit.
Your task is to implement on Ed a reduction from the 3D Rotational Fit Problem to the 3D Non-
Rotational Fit Problem. In particular, your algorithm should take as input an instance I of the 3D
Rotational Fit Problem and output an instance J of the 3D Non-Rotational Fit Problem such that the
total rotational fit of I is exactly equal to the total non-rotational fit of J . For full marks, your algorithm
should run in linear time, i.e. O(n+m) time.
Task 3 (COMP3027 and COMP3927): The Wurst-Ka¨se Scenario
[70 marks]
The Best Wurst-Ka¨se Festival is on! The festival celebrates the best sausage and cheese shops throughout
Sydney. Each shop o?ers a sausage and cheese tasting platter. You are given, in the form of a graph,
1This is actually my initial thought process when I came up with this problem (minus the Rubber Duck).
2
a map of the locations of various shops and a start and end location. In the interest of maintaining a
balanced diet2, you want to find a path from start to finish such that the total amount of cheese collected
equals the total amount of sausage collected. More formally, you are given a directed graph G = (V,E)
with a start vertex s, and an end vertex t. You are also given, for every vertex v, the amount of sausage
Sv 0 and the amount of cheese Cv 0 of the platter o?ered by the shop at vertex v. A simple path P
is said to be balanced if the total amount sausage on the path equals the total amount of cheese on the
path, i.e.
P
v2P Sv =
P
v2P Cv. The goal is to decide if there is a balanced path from s to t. We call
this the Wurst-Ka¨se Path Decision problem.
In the below example, Ss = 1, Cs = 0, Su = 1, Cu = 2, Sv = 2, Cv = 1, St = 0 and Ct = 1. The path
s u t has 2 sausages and 3 cheeses, so it’s imbalanced. On the other hand, the path s v u t has
4 sausages and 4 cheeses, so it’s balanced. Thus, this is a YES-instance.
s
u
v
t
Your task is to show that the Wurst-Ka¨se Path Decision problem is NP-complete.
(a) First show that the problem is in NP
(i) Describe a certificate and a verifier.
(ii) Give a brief justification of the correctness of the verifier.
(iii) Give a brief justification that the verifier runs in polynomial time.
(b) To show that the problem is NP-hard, give a polynomial-time Karp reduction from the Partition3
problem.
(i) Describe how you transform an instance of the Partition problem into an instance of the
Wurst-Ka¨se Path Decision problem.
(ii) Prove the correctness of your reduction, i.e. the instance of the Partition problem is a YES-
instance if and only if the instance of the Wurst-Ka¨se Path Decision problem created by your
reduction is a YES-instance.
(iii) Prove that your reduction is polynomial-time.
Submission details
? Please do not submit in German.
? Submission deadline is Friday 13 May, at 23:59. Late submissions without special consider-
ation will be subject to the penalties specified in the first lecture (5% per day). . Submissions
later than Sunday 15 May, 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.
? 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 as the precise algorithms, examples, proofs, writing, or code.
To facilitate anonymous grading, please do not write your name on your submission.
Level of detail required in this assignment
Please do not write pseudocode (it’s an unnecessarily precise level of detail for these reductions,
and usually harder to follow than prose.)
Please try to be fairly concise.
It’s reasonable to write things like these without having to explain precisely how it’s done:
– ‘check that P is a simple path’
– ‘check that all the subsets are disjoint’
You don’t need to detail data structures etc., unless the choice of structure is important for showing
that the time complexity is still polynomial.
Don’t forget that you’re not trying to solve these problems, you only need to find polynomial time
certifiers / polynomial time reductions as appropriate.