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 Questionsdocument, 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.

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 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.

1.4   [8  marks] Design an algorithm that runs in O(nlog n) time and determines a minimal sequence of actions to reduce each building’s height to 0.

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(nlog 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 array M[1..n] and B[1..n] of customers’ minimum prices and budgets, design an algorithm which runs in O(n2 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] 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 are M = [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] = {0(1)

if customer i is free on day j

otherwise

design an algorithm which runs in O(n2 m) 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 least M[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].