COMP3121/9101 22T3 — Assignment 3 (UNSW Sydney)
Due 27th October 2022 at 5pm Sydney time
Your solutions must be typed, machine readable PDF files. All submissions will be checked for
plagiarism!
For each question requiring you to design an algorithm, you must justify the correctness of your
algorithm. If a time bound is specified in the question, you also must argue that your algorithm
meets this time bound.
Partial credit will be awarded for progress towards a solution.
Please note that for max flow algorithms you must clearly detail any graphs you are con-
structing. This means describing all vertices, edges, capacities, sources, and sinks. Diagrams
(either neatly hand-drawn or in LaTeX) are also encouraged as a supplement. In terms of
quoting known max flow algorithms, you may only quote the ones taught in lectures (i.e. Ford-
Fulkerson or Edmonds-Karp). To justify the correctness of a max flow algorithm, you must
explain why your algorithm result satisfies all conditions imposed by the problem. Roughly
10% of the total marks will be specifically allocated towards the clarity and conciseness of
your explanations.
Question 1 Arc Competition
[20 marks] Arc is hosting a training session for the members of various societies at UNSW. There
are n students who are Arc members, and m < n registered societies. Each of the n students is a
member of at least 1 and at most 4 of the m societies. Each of the m societies must send exactly
1 student to represent them at the training session.
In order to keep the crowd diverse, Arc would like to avoid all of the student representatives
studying degrees from the same faculty. Each of the n students is enrolled in a single degree
offered by 1 of the k ≤ n faculties at UNSW. For every faculty i ∈ [1..k], at most ui students
belonging to it will be allowed to attend the event.
Design an O(nm) algorithm that determines if it is possible to find a selection of students to attend
the event such that all of these criteria are met. If it is possible, also identify which m students
will attend.
Question 2 Pirate Gathering
[30 marks] Somewhere in the Caribbean there are V islands labeled 1..V andN pirate ships named
1..N . Additionally there are E two-way routes, the ith of which allows a ship to sail between island
ui and island vi. However, the pirates are fiercely territorial and hence each direction of a route
can only be used by one pirate ship. That is, if ship x has traveled from island u to island v,
another ship y can still travel from island v to island u.
The pirate ships are initially on unique islands {h1, h2, . . . , hN}, and wish to gather on island
T ∈ [1, ..., V ].
2.1 [18 marks] Design an O(NE) algorithm which determines whether or not it is possible for
every pirate to reach the designated island, T .
2.2 [6 marks] In an attempt to prevent the gathering, the government has now imposed a
restriction that at most si pirate ships are allowed to depart from island i.
Design an O(NE) algorithm which determines whether every pirate can still reach the designated
island. You may reference your answer from Question 2.1 and only provide the details and justifi-
cation of any modifications.
1
COMP3121/9101 22T3 — Assignment 3 (UNSW Sydney)
You may choose to skip Question 2.1 in which case your solution to Question 2.2 will be
submitted for both parts.
2.3 [6 marks] The location of the designated island T has been leaked to the government and it
may no longer be safe. The pirates want to know if there any other options where all pirates can
gather, given the same restrictions as Question 2.2. Design an O(V EN) algorithm that counts the
number of islands are suitable for the gathering (including island T ).
You may reference your answer from Question 2.2 and only provide the details and justification of
your modifications, which must also include an updated time complexity justification.
Question 3 CSE Labs
[30 marks] The School of CSE is scheduling some labs for its classes. There are n classes that
need to be scheduled into one of the n available labs, and they would like all of the labs to run at
the same time. A single class cannot occupy multiple labs, and multiple classes also cannot share
a lab.
3.1 [4 marks] For a class to use a lab, there has to be at least 1 seat for each student. Given an
array C[1...n] where C[i] indicates the number of students in class i, and an array L[1...n] where
L[j] indicates the number of seats in lab j, design an O(n log n) time algorithm that assigns a lab
room to each class. Your algorithm should also identify if an assignment is not possible.
3.2 [7 marks] It turns out that classes are very picky about which labs they want. In particular,
you are now provided an additional array B[1..n][1..n] with
B[i][j] =
{
True class i likes lab j
False otherwise
Given C[1..n], L[1..n] and B[1..n][1..n], design an O(n3) algorithm to assign a lab room to each
class. Your algorithm should also identify if an assignment is not possible.
3.3 [12 marks] Unfortunately an issue with the building has affected the power and now there
are only m < n labs available. The school has no choice but to schedule some classes at different
times. Given the arrays C[1...n], L[1...m], B[1..n][1..m] defined as in the previous parts, design an
O(n3) time algorithm that determines whether it is possible to schedule the classes with T < N
different time slots available.
3.4 [7 marks] Each of the classes also requires one of k ≤ n tutors to run the lab. Each tutor is
only allowed to run a maximum of 3 labs, and can only run 1 lab at a time. The tutors’ availability
is given as an array D[1..k][1..T ] with
D[i, j] =
{
1 if the ith tutor is available at timeslot j
0 otherwise
For some number of timeslots T < n, design an O(n3) algorithm that assigns a room, time, and
tutor to each lab if a schedule is possible.
Question 4 Spy Escape
[20 marks] Agency X has sent n spies to Sydney for a secret mission. Before the mission begins,
Agency X has prepared m > n secret hideouts throughout the city, of which n of them contain
2
COMP3121/9101 22T3 — Assignment 3 (UNSW Sydney)
a single emergency escape pod. The hideouts are connected via a network of tunnels, and each
hideout can only accommodate one spy at a time. The emergency escape pods can also only
accommodate one spy. Everyday, the spies can crawl through at most one tunnel to reach a new
hideout.
The tunnels are represented by an adjacency matrix T [1..m][1..m], where
T [i][j] =
{
True hideout i has a tunnel to hideout j
False otherwise
4.1 [14 marks] A few days after the mission began, all spies have been compromised. The spies
are currently scattered around the hideouts in Sydney and must make it to an emergency escape
pod within D days to avoid capture.
Design an O(nm2D) algorithm which determines whether or not all spies can successfully es-
cape.
Try to first solve this for D = 1, and then consider how would you could extend this for D = 2
and greater.
4.2 [6 marks] Despite the compromise, Agency X still wants to wrap up some tasks in Sydney
before the spies escape. The spies will die if they are not done in D days.
Design an O(nm2D logD) algorithm to determine the minimum number of days needed for all
spies to successfully escape.