COMP3121/9101 22T3 — Assignment 4
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 all Dynamic Programming solutions we expect you to clearly state a
subproblem, a recurrence relationship, base cases, and how the final answer can be obtained.
These element should all be related and in sync with each other! To justify the correctness of
a Dynamic Programming solution, you need to explain (in words) how your recursion handles
all necessary cases in the problem and why each case is correct. Roughly 10% of the total
marks will be specifically allocated towards the clarity and conciseness of your explanations.
1
COMP3121/9101 22T3 — Assignment 4 (UNSW Sydney)
Question 1 Bridge Support
[20 marks] The NSW government has decided to build a new bridge. The bridge is to be n meters
long, where A[i] is the maximum load on the bridge between (i? 1) meters and i meters.
The government have contracted you to complete this project, and you’ve decided to build the
bridge in spans of integer length. The cost of building a span is given by the length of the span
squared, plus the maximum load that the span needs to withstand. The total cost of building the
bridge is the sum of the cost of all spans. More explicitly:
total cost =
∑
s∈spans
(sR ? sL)2 +max(A[(sL + 1)..sR])
where sL and sR are the left and right endpoints respectively of the span s.
Your goal is to determine the minimum cost required to build a bridge that supports the
load.
An example for the cost calculation: if n = 5 and A = [3, 5, 10, 2, 6], and you decided to put
pillars in at 2 meters and 4 meters, the total cost would be:
span [0,2] = (2? 0)2 +max(A[1..2]) = $9
span [2,4] = (4? 2)2 +max(A[3..4]) = $14
span [4,5] = (5? 4)2 +max(A[5..5]) = $7
total cost = $9 + $14 + $7 = $30
A depiction of this example is shown in image below.
3 5 10 2 6
1.1 [14 marks] Design an O(n3) algorithm which achieves your goal.
1.2 [6 marks] With an election looming, the NSW government has asked you to hurry up.
Design an algorithm that achieves the goal in O(n2).
You may choose to skip Question 1.1, in which case your solution to Question 1.2 will also be
submitted for Question 1.1.
2
COMP3121/9101 22T3 — Assignment 4 (UNSW Sydney)
Question 2 Mountain Radios
[30 marks] Alice and Bob are bored of the park, and have decided to go mountaineering! They
will each be traversing the mountain and moving through a sequence of n camps. Both Alice and
Bob will always spend the night at one of their camps. Alice’s camps are given by a sequence
of coordinates pairs A1, ..., An, where Ai = (Aix , Aiy ), and Bob’s camps are given as B1, ..., Bn,
where Bj = (Bjx , Bjy ). On the first night, Alice will spend the night at camp A1 and Bob will
spend the night at camp B1. Each day, both Alice and Bob have the choice of staying at their
current camp or moving to the next camp in their sequence. They can never move back to a camp
they have previously visited. At least one of them must move each day, meaning that both Alice
and Bob will have reached their final camps no later than the (2n? 1)th night.
Alice and Bob would like to be able to talk to each other at night via a radio, but all of the
wireless radios available for purchase have a fixed range. Alice has noticed that if they care-
fully plan who moves to the next camp on each day, it will affect how far apart they get dur-
ing their journey. The distance between two coordinates (x1, y1) and (x2, y2) is calculated as
d =
√
(x2 ? x1)2 + (y2 ? y1)2.
For example, let n = 5 and A1 = (1, 1), A2 = (3, 1), A3 = (4, 1), A4 = (5, 1), A5 = (6, 1),
B1 = (1, 2), B2 = (2, 2), B3 = (3, 4), B4 = (4, 2), B5 = (6, 2). In this example, the furthest
apart Alice and Bobmust get during their journey is 3 units. One way this could be achieved is
with the sequence of stays [(A1, B1), (A2, B2), (A2, B3), (A2, B4), (A3, B4), (A4, B5), (A5, B5)].
With this sequence of moves, the furthest apart that Alice and Bob get is on night 3, when
Alice is at A2 and Bob is at B3.
Figure 1: The simple example described above. The blue line represents the path Alice will walk
and the green line represents the path Bob will walk. The red line shows the furthest apart Alice
and Bob must get during their journey.
3
COMP3121/9101 22T3 — Assignment 4 (UNSW Sydney)
2.1 [15 marks] Design an O(n2) algorithm to determine whether a radio with a range of D will
allow them to communicate every night.
In the provided example, your method should determine that it is impossible for any value of
D < 3, and possible otherwise.
2.2 [15 marks] Design an O(n2) algorithm that calculates the minimum range required for Alice
and Bob to be able to communicate every night.
In the provided example, your method should calculate a minimum required range of 3.
You can receive up to 7 marks for an O(n2 log n) solution.
You may choose to skip Question 2.1, in which case your solution to Question 2.2 will also be
submitted for Question 2.1.
4
COMP3121/9101 22T3 — Assignment 4 (UNSW Sydney)
Question 3 KFC Now!
[20 marks] There are n ≥ 0 people queuing for KFC. The ith person has an hunger of hi, and
everyone in line has a distinct hunger. A person’s ‘annoyance’ is defined as the number of people
in front of them who are less hungry, and the annoyance of the entire queue is the sum of every
person’s annoyance.
Given the hunger of every person, your goal is to determine how many arrangements of the queue
will result in a total annoyance of exactly k.
As always, you can assume that all arithmetic operations (+?×/) are done in constant time.
3.1 [12 marks] Design an O(n2k) algorithm that achieves the goal.
3.2 [8 marks] Design an O(nk) algorithm which achieves the goal.
You may choose to skip Question 3.1, in which case your solution to Question 3.2 will also be
submitted for Question 3.1.
5
COMP3121/9101 22T3 — Assignment 4 (UNSW Sydney)
Question 4 Antoni the Merchant
[30 marks] Antoni wants to earn as much money as possible over the summer holidays as a
travelling merchant in the DynaProg continent. He will begin his journey with $0 wealth, and
he only has D days before term starts and he is pulled back into answering forum questions, so
he needs to plan very carefully. After thorough research, he has found n countries where he can
turn an easy profit; in fact, he knows that if he is in country i ∈ [1..n] on day d ∈ [1..D], he is
guaranteed to earn P [i][d] > 0 dollars.
All n countries have airports, and a direct flight to every other country. Each day Antoni can
either travel to another country, or stay where he is. There is no restriction on how many times
he can visit a certain country, nor on the number of days he can stay per visit.
However, the tax laws in DynaProg are vicious - every day he is taxed a percentage of his current
wealth. Specifically, you are given a Tax Table T [1..n][1..n] where 0 ≤ T [j][i] ≤ 100 is the percentage
Antoni will be taxed if he is currently in country j and was in country i the previous day. He is
not taxed anything on the first day as he has $0 wealth.
Help Antoni prepare a full itinerary (which country to be in on every day) that maximises his
wealth by the end of D days.
Tax is deducted before the earnings are added for the day.
On Day 1, Antoni will not be taxed since his wealth is $0 and there is nothing to deduct. He
will then earn $P [i][1] for whichever country i he has chosen to start at.
On Day 2, he can either stay in country i, or travel to another country j. If he chooses to
stay, he will be taxed T [i][i]% of his current wealth, and then earn $P [i][2]. If he chooses to
travel, he will be taxed T [j][i]% of his current wealth, and then earn $P [j][2].
4.1 [12 marks, 4 marks per part] Antoni has prepared a few Greedy approaches to solving
this problem, but is not convinced they will always earn him the most money.
Provide a counter example for each of the following approaches. Your counter example must state
the values for n,D, P, T , the wealth Greedy obtains and its itinerary, and finally, a more optimal
wealth and the itinerary used to attain it. The more optimal solution does not have to be the best,
it just has to beat Greedy.
[A] On each day d, travel to the country where Antoni will earn the most money (i.e. travel to
the country i such that P [i][d] is maximised, for all days 1 ≤ d ≤ D). If there is a tie, choose
the country with the lower tax rate.
[B] First, travel to the country with the highest Day 1 profit (i.e. travel to the country i such that
P [i][1] is maximised). Then, on each subsequent day d, travel to the country that minimises
the amount of tax (in dollars) that Antoni will be charged (i.e. travel to the country j such
that T [j][i]%× current net wealth is minimised, for all days 2 ≤ d ≤ D). If there is a tie,
choose the country with the higher profit.
[C] First, travel to the country with the highest Day 1 profit. Then, on each subsequent day d,
travel to the country that maximises Antoni’s wealth at the end of the day (i.e. travel to the
country j such that current net wealth × (100 ? T [j][i])% + P [j][d] is maximised, for all
days 2 ≤ d ≤ D). Break ties arbitrarily.
4.2 [18 marks] Design an O(n2D) algorithm that finds the maximum possible wealth Antoni
can attain, and also provides the itinerary he needs to follow.