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:

• length(pi) length(bj), width(pi) width(bj) and height(pi) height(bj) or

• width(pi) length(bj), length(pi) width(bj) and height(pi) height(bj) or

• height(pi) length(bj), width(pi) width(bj) and length(pi) height(bj) or

• width(pi) length(bj), height(pi) width(bj) and length(pi) height(bj) or

• length(pi) length(bj), height(pi) width(bj) and width(pi) height(bj) or

• height(pi) length(bj), length(pi) width(bj) and width(pi) height(bj).

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.

• Familiarize yourself with following Ed posts and resources:

– General Assignment Guidelines https://edstem.org/au/courses/7844/discussion/752742

2See http://phdcomics.com/comics/archive.php?comicid=12

3See Tutorial 9.

3

– How to Approach Problems https://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.

• 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.

4

欢迎咨询51作业君