COMP3121/9101 23T1 — Assignment 3 (UNSW Sydney)
Due Friday 14th April at 5pm Sydney time
In this assignment we apply dynamic programming and associated graph algorithms. There are
three problems each worth 20 marks, for a total of 60 marks. Partial credit will be awarded for
progress towards a solution. We’ll award one mark for a response of “one sympathy mark please”
for a whole question, but not for parts of a question.
Any requests for clarification of the assignment questions should be submitted using the Ed forum.
We will maintain a FAQ thread for this assignment.
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. The required time bound always applies to the worst case unless otherwise
specified.
You must submit your response to each question as a separate PDF document on Moodle. You
can submit as many times as you like. Only the last submission will be marked.
Your solutions must be typed, not handwritten. We recommend that you use LaTeX, since:
as a UNSW student, you have a free Professional account on Overleaf, and
we will release a LaTeX template for each assignment question.
Other typesetting systems that support mathematical notation (such as Microsoft Word) are also
acceptable.
Your assignment submissions must be your own work.
You may make reference to published course material (e.g. lecture slides, tutorial solutions)
without providing a formal citation. The same applies to material from COMP2521/9024.
You may make reference to either of the recommended textbooks with a citation in any
format, except that you may not use network flow algorithms not presented in lectures.
You may reproduce general material from external sources in your own words, along with a
citation in any format. ‘General’ here excludes material directly concerning the assignment
question. For example, you can use material which gives more detail on certain properties of
a data structure, but you cannot use material which directly answers the particular question
asked in the assignment.
You may discuss the assignment problems privately with other students. If you do so, you
must acknowledge the other students by name and zID in a citation.
However, you must write your submissions entirely by yourself.
Do not share your written work with anyone except COMP3121/9101 staff, and do not
store it in a publicly accessible repository.
– The only exception here is UNSW Smarthinking, which is the university’s official writing
support service.
Please review the UNSW policy on plagiarism. Academic misconduct carries severe penalties.
Please read the Frequently Asked Questions document, which contains extensive information about
these assignments, including:
how to get help with assignment problems, and what level of help course staff can give you
extensions, Special Consideration and late submissions
an overview of our marking procedures and marking guidelines
how to appeal your mark, should you wish to do so.
1
COMP3121/9101 23T1 — Assignment 3 (UNSW Sydney)
Question 1
Given a strictly increasing sequence A whose entries are positive integers [a1, . . . , an], a sub-
sequence of A is defined by removing zero or more elements from A while preserving the original or-
der. For example, [1, 13, 21] and [1, 2, 3, 13, 18, 21, 71] are both sub-sequences of [1, 2, 3, 13, 18, 21, 71].
A sequence x1, x2, ..., xm is called beautiful if:
m ≥ 3, that is, the number of elements in the sequence is greater or equal to 3.
3xi + 5xi+1 = xi+2 for all i ≤ n? 2.
In the example above, the beautiful sub-sequences are:
[1, 2, 13],
[1, 3, 18],
[2, 3, 21],
[2, 13, 71] and
[1, 2, 13, 71].
1.1 [5 marks] Suppose [. . . , aj , ak] is a beautiful sub-sequence of A. Given the indices j and
k of the last two entries of the sub-sequence, design an algorithm which runs in O(log n) time
and computes the index in A of the third last entry of the sub-sequence.
Your algorithm should find the index i of the entry ai which precedes aj and ak in the
sequence, assuming that such an i exists.
1.2 [12 marks] Design an algorithm which runs in O(n2 log n) time and computes the length
of the longest beautiful sub-sequence of A.
We believe this problem can be solved in O(n2) time. A solution satisfying this constraint
will earn one bonus mark for the course.
1.3 [3 marks] Design an algorithm which runs in O(n log n) additional time and lists the
entries of the longest beautiful sub-sequence of A.
‘Additional’ here means after the execution of your algorithm for 1.2.
If there are two or more equal longest beautiful sub-sequences, your algorithm should produce
any one of them.
2
COMP3121/9101 23T1 — Assignment 3 (UNSW Sydney)
Question 2
You are in a warehouse represented as a grid with m rows and n columns, where m,n ≥ 2. You are
initially located at the top-left cell (1, 1), and there is an exit at the bottom-right cell (m,n). There
are certain cells that contain boxes which you can not move through. The grid is given as a 2D
array B[1..m][1..n] where B[i][j] is True if cell (i, j) contains a box and False otherwise.
2.1 [6 marks] Occupational health and safety regulations specify that it must be possible
to reach the exit from your starting point by making only two kinds of moves: down one cell
or right one cell. Design an algorithm that runs in O(mn) time and determines whether the
warehouse layout meets this requirement.
Note: there is both a DP and a non-DP approach to this question. Both are eligible for full
marks in this part, but the DP approach naturally lends itself to be extended to Question 2.2.
If you choose the non-DP approach here, you will likely need to put in more work to get full
marks in Question 2.2.
2.2 [3 marks] Unfortunately, some warehouse layouts do not meet this requirement. You
have been asked to remove some boxes to ensure that the requirement is met, but wish to
remove as few as possible to make efficient use of warehouse space. Design an algorithm that
runs in O(mn) time and determines the smallest number of boxes that must be removed to
meet the requirement.
The fire alarm has gone off, so you have to make your escape! Fortunately, this warehouse passed
the safety inspection, so you know there is a path to the exit that only involves moving down
or right one cell at a time. However, you also want to ensure you can make a speedy escape, so
you must take exactly one shortcut by moving diagonally: one cell down and right at the same
time.
For example, the red path through this warehouse includes a shortcut from (2, 2) to (3, 3).
B
B
2.3 [2 marks] Show that any warehouse passing the safety requirement from 2.1 has a path
from (1, 1) to (m,n) that includes a shortcut.
2.4 [9 marks] Each cell of the warehouse that does not contain a box has a particular hazard
rating H[i][j], and you want to minimise the sum of the hazard ratings on your path to the
exit.
For example, the red path through this warehouse layout has a total hazard rating of 13, takes
exactly one shortcut, and is the minimal path for this particular warehouse.
2 2 6 1
3 4 B 1
2 B 2 2
1 4 2 1
Design an algorithm that runs in O(mn) time and determines the minimum total hazard rating
you can achieve.
3
COMP3121/9101 23T1 — Assignment 3 (UNSW Sydney)
Question 3
You have been asked to perform n complex calculations c1, . . . , cn, where each calculation ci requires
ri bytes of RAM to store the result. You can perform the calculations in any order.
Some calculations depend on the result of others. These dependencies are represented as a directed
graph G = (V,E), where E contains an edge cj → ci if the result of cj has to be in RAM in order
to calculate ci.
Let pred(i) denote the set of computations that ci depends on, that is,
pred(i) = {j : (cj → ci) ∈ E}.
3.1 [3 marks] Explain why it is impossible to perform all n calculations unless the graph G
is acyclic.
3.2 [10 marks] To perform calculation ci, we first have to collate the results of pred(i), which
takes ∑
j∈pred(i)
rj
seconds. It then takes r2i seconds to compute the result.
On a sequential computer which can only perform one calculation at a time, it takes
seconds to determine all results. However, we have a massively parallel computer that can
perform an unlimited number of calculations at the same time.
Design an algorithm that runs in O(n+m) time and determines the minimum amount of time
required to perform all n calculations on the parallel computer, where m is the number of
dependencies, i.e. the number of edges in the graph.
3.3 [7 marks] We now have access to a supercomputer which can compute results instantly.
If we choose to use the supercomputer for calculation ci, it takes only∑
j∈pred(i)
rj
time to collate the previous results, without the additional r2i seconds to compute the re-
sult.
The supercomputer is very expensive to run, so it can be used at most s times.
Design an algorithm that runs in O(s(n +m)) time and determines the minimum amount of
time required to compute all n results using the supercomputer for at most s calculations, and
the parallel computer for all other calculations.