[SOLVED] COMP3121/9101 Assignment 3 

Question 1
Given a strictly increasing sequence A whose entries are integers [a1,…,an], a sub-sequence of
A is defined by removing zero or more elements from A while preserving the original order. 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 […,xj , xk] 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 of the third last entry of the sub-sequence.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.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 ecient 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 o↵, 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 1Design an algorithm that runs in O(mn) time and determines the minimum total hazard rating
you can achieve.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) 2 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
X
j2pred(i)
rj
seconds. It then takes r2
i seconds to compute the result.On a sequential computer which can only perform one calculation at a time, it takes
Xn
i=1
0
@r2
i + X
j2pred(i)
rj
1
Aseconds 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
X
j2pred(i)
rj
time to collate the previous results, without the additional r2
i seconds to compute the result.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.