COMP3121/9101 23T1 — Assignment 2 (UNSW Sydney)
Due Monday 27th March at 5pm Sydney time
In this assignment we apply the greedy method and associated graph algorithms, including algo-
rithms for network flow. 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 2 (UNSW Sydney)
Question 1
A demolition company has been tasked with taking down n buildings, whose initial heights are
positive integers given in an array H[1..n]. The company has two tools at its disposal:
a small explosive, which reduces the height of a single building by 1, and
a wrecking ball, which reduces the height of all buildings by 1.
The company has an unlimited supply of the small explosives, which are free to use. However, the
wrecking ball costs $1000 each time it is used.
The company initially has $1000 dollars. They also get $1000 whenever they finish the demolition
of a building with the wrecking ball (reducing its height from 1 to 0), but they receive no money if
the demolition of a building is finished using an explosive.
For example, for four buildings of heights [2, 3, 5, 1], the following sequence of actions demolishes
all buildings.
Use a small explosive on building 1, resulting in [1, 3, 5, 1].
Spend the $1000 to use the wrecking ball, resulting in heights [0, 2, 4, 0]. Buildings 1 and 4
were demolished, so the company receives $2000.
Use the wrecking ball again, leaving heights [0, 1, 3, 0]. No buildings were demolished, so no
money is gained.
Use an explosive to demolish building 2, giving [0, 0, 3, 0]. No money is awarded for completing
the demolition of building 2, since the wrecking ball was not used.
Use explosives three times to demolish building 3.
A sequence of actions is minimal if it demolishes all the buildings and there is no shorter sequence
of actions that does this. The sequence above is not minimal.
1.1 [2 marks] Find a minimal sequence of actions to demolish all four buildings in the example
above, where the heights are 2, 3, 5 and 1. You must provide reasoning for why your sequence is
minimal.
1.2 [6 marks] Show that there is always a minimal sequence of actions that results in the
buildings being demolished where all uses of the explosive occur before any uses of the wrecking
ball.
1.3 [4 marks] Identify a criterion for whether there is a minimal sequence of actions to demolish
all buildings using only the wrecking ball, with reasoning to support it.
Your criterion should be a test which given n and the array H answers Yes if there is any
minimal sequence using only the wrecking ball, or No otherwise.
1.4 [8 marks] Design an algorithm that runs in O(n log n) time and determines a minimal
sequence of actions to reduce each building’s height to 0.
2
COMP3121/9101 23T1 — Assignment 2 (UNSW Sydney)
Question 2
You run a jewellery shop and have recently been inundated with orders. In an attempt to satisfy
everyone, you have rummaged through your supplies, and have found m pieces of jewellery, each
with an associated price. To make things easier, you have ordered them in increasing order of their
price. You now need to find a way to allocate these items to n ≤ m customers, while minimising
the number of customers who walk away with nothing.
2.1 [8 marks] Each customer has a minimum price they will pay, since they all want to impress
their significant others. Of course, you need to decide who gets what quickly, or else everyone will
just leave to find another store.
Given an array P [1..m] of jewellery prices, sorted in ascending order, and an array M [1..n] of
customers’ minimum prices, design an algorithm which runs in O(n log n+m) time and allocates
items to as many customers as possible, such that the price of the item given to customer i is at
least M [i], if they are given an item at all.
For example, suppose the store has m = 5 pieces of jewellery with prices P = [5, 10, 15, 20, 25], and
the minimum prices of the n = 3 customers are M = [21, 15, 31]. In this case, the first customer
can get the $25 item, and the second customer can get the $15 item or the $20 item. However,
the third customer will walk away as the store does not have any jewellery that is priced at $31 or
higher.
2.2 [8 marks]With a sigh of relief, and an allocation set up, you go to ring up the first customer’s
item, just to find out that they can’t afford it! In a panic, you get everyone to give you their budgets,
and go back to the drawing board.
Given an array P [1..m] of jewellery prices, sorted in ascending order, and arrayM [1..n] and B[1..n]
of customers’ minimum prices and budgets, design an algorithm which runs in O(n2m) time and
allocates items to as many customers as possible, such that the price of the item given to customer
i is at least M [i] and doesn’t exceed B[i], if they are given an item at all.
For example, the store has m = 5 pieces of jewellery with prices P = [5, 10, 15, 20, 25]. The
minimum prices of the n = 3 customers areM = [21, 16, 31], and their budgets are B = [26, 19, 38].
In this case, the first customer can get the $25 item, but the second customer has to walk away as
he refuses the $5, $10 and $15 items but cannot afford the $20 and $25 items. The third customer
will also walk away as the store does not have any jewellery that is priced at $31 or higher.
2.3 [4 marks] There are only k < m days until Valentine’s day, and all of your customers need
to get their orders before then. Unfortunately, you are only able to process a total of five orders
per day. To make matters worse, each customer is only available to pick up their orders on some
of the days.
Given an array P [1..m] of jewellery prices, sorted in ascending order, arrays M [1..n] and B[1..n]
of customers’ minimum prices and budgets, and an array F [1..n][1..k] where
F [i][j] =
{
1 if customer i is free on day j
0 otherwise
design an algorithm which runs in O(n2m) and allocates items and assigns collection days to as
many customers as possible, such that the price of the item given to customer i is at leastM [i] and
doesn’t exceed B[i] if they are given an item at all, and they are free on their assigned collection
day.
For example, the store has m = 5 pieces of jewellery with prices P = [5, 10, 15, 20, 25]. The
minimum prices of the n = 3 customers are M = [21, 16, 31] and their budgets are B = [26, 19, 38].
3
COMP3121/9101 23T1 — Assignment 2 (UNSW Sydney)
The array F [1..n][1..k] has entries F [1][1], F [2][1], F [2][2] and F [3][2] equal to 1, and everything
else set to 0, representing customers 1 and 2 free on day 1, and customers 2 and 3 free on day 2. In
this case, the number of purchases is less than 5 on both days, so for the same reasons described
in 2.2, only the first customer can get jewellery.
Question 3
You are studying the ancient Antonise language, and are trying to create some kind of alphabet for
it. You have scoured the texts and figured out that there are g many glyphs in this language, but
you don’t know the order of the alphabet, and want to figure out what it might be. Thankfully,
you have found a tome with n unique names, all conveniently k glyphs long, which you suspect are
in alphabetical order, and hope to find a way to rearrange the glyphs into an alphabet consistent
with the order of the names. For example, suppose your tome contained the following n = 3 names,
consisting of k = 3 glyphs each, from g = 5 possible glyphs:
(oX ,
((o ,
X?K .
Then both o(X?K and o(XK? would be possible alphabets, as the names are in
alphabetical order with respect to either of these. However,(oX?K would not, as the names
(oX and ((o would be out of order with respect to any alphabet where ( comes before
o .
3.1 [4 marks] Provide a small example of a tome of at most five names, each of length at most
four glyphs, which are not in alphabetical order regardless of how you rearrange the glyphs to form
an alphabet.
You must list the names in the order they are found in the tome, and briefly explain why they
cannot be in alphabetical order, no matter what order the glyphs are arranged into an alphabet.
You may use any symbols for the glyphs in this example, such as the dingbats used in the question,
English letters, or numbers.
3.2 [16 marks] You are given the number of glyphs g, the number of names n, the number of
glyphs in each name k, and a two-dimensional array S[1..n][1..k] containing the numbers 1 through
g, where S[i] is an array containing the i
th
name, and S[i][j] is the index of the j
th
glyph in that
name. The original indexing is arbitary, and the names may not be in alphabetical order with
respect to this indexing.
Design an algorithm which runs in O(nk+g) time and finds an alphabet (i.e. reindexes the glyphs)
so that the names in S are in alphabetical order if this is possible, or otherwise determines that
no such alphabet exists.
An algorithm which runs in Θ(n2k + g) time will be eligible for up to 12 marks.