In this assignment we apply the greedy method and associated graph algorithms, including algorithms 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

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

Question 1 Housing Crisis

Even is a corrupt developer who has k dollars in the bank, and owns n plots of land where the ith plot has a value of vi dollars. Even would like to build a high-rise apartment building on each plot, but is currently unable to do so due to low-density zoning restrictions imposed by local council.

In order to build apartments on the ith plot, Even must bribe the council with vi dollars to get the land re-zoned. Alternatively, he can sell the ith plot and receive vi dollars. Each plot can either be rezoned, sold, or left alone.

For example, if Even starts with 12 million dollars and has plots with values (in millions) [10, 11, 9], he can:

1. develop plot 1 by bribing 10 million dollars, leaving him with 2 million dollars

2. sell plot 3, gaining 9 million dollars and leaving him with 11 million dollars

3. develop plot 2 by bribing 11 million dollars.

1. 1. [10 marks] Design an O(n log n) algorithm that finds the largest number of apartment buildings Even can build.

   2. [10 marks] The Developer’s Association has a program to encourage selling plots: For the

      1. sell plot 6, gaining 10×2=20 million dollars and leaving him with 25 million dollars

      2. sell plot 4, gaining 8×3=24 million dollars and leaving him with 49 million dollars

      3. develop plot 2 by bribing 6 million dollars, leaving him with 43 million dollars

      4. develop plot 3 by bribing 7 million dollars, leaving him with 36 million dollars

Given that the value list vi is sorted, design an algorithm that runs in O(n) time which determines the largest number of apartments Even can build when joining this program.

An O(n2) or O(n log n) algorithm will be worth at most 8/10 marks

Question 2 Ruins

Your boss has decided to take everyone on a mandatory vacation to a ruin. To be on the safe side of the law, they haven’t said anything explicitly, but have very strongly suggested everyone should look for treasure to hand in at the end of the trip.

All k employees have entered the ruins and located a piece of treasure each. However, an earthquake has struck, and the ruins have started to collapse. There are conveniently exactly k rooms with a stairwell to escape from, but every time someone travels to an adjacent room, the doorway collapses, so no door can be used twice, and are too small to let more than one person through them at a time. After leaving the stairwell, it collapses, so only one employee can escape using each stairwell.

You are given a graph G with n vertices and m edges, where each vertex represents a room, and each edge represents a doorway connecting adjacent rooms. You may assume that n < m. You are also given two arrays, E[1..k] and X[1..k], being a list of rooms with an employee and a list of rooms with a stairwell respectively.

2.1 [10 marks] Your boss, ever greedy, has started freaking out about rescue costs, and wants to know exactly how many employees will be able to escape. Thankfully, they had the foresight to give everyone in the ruin a communication device, so everyone can communicate as they escape to coordinate their paths. Determine the maximum number of employees that can escape the ruins in O(k(m + k)) time.

You are given another array, T [1..n] where T [i] is true if the room represented by vertex i contains an active teleporter, and false otherwise. Determine the maximum number of employees that can escape the ruins now that teleporters can be used, without teleporting more than C times in total, in O(k(m + k)) time.

2.3 [5 marks] Your boss has found a large supply of gold coins to use to power the teleporter, but wants to keep as many gold coins as they can for themselves. Determine the maximum number of employees that can escape the ruins, while minimising the number of uses of the teleporter, in O(k(m + k) log k) time.

If there is a solution that allows more employees to escape, but requires more uses of the teleporter, it should be chosen instead.

Question 3 Song the Cybercriminal

Gerald wants to send Blake an l-byte message containing the 3121 assignment answers over a network made up of n routers with m links between them. The network is represented as a connected undirected graph G = (V, E), where Gerald’s router is v1 and Blake’s is vn. Each link ei in the network has a maximum transmission unit (MTU) ti, which is the largest number of bytes that can be sent over the link in one transmission.

In each transmission, Gerald must choose a path through the network, then send all the bytes for that transmission along the path. The maximum size of the transmission is the smallest MTU of all the links on the path. He can change paths between transmissions.

2

v2           4          v5

4

2

v1             2            v4             2            v7

For example, in this network, Gerald can send 3 bytes per transmission using the path v1 → v3 → v6 → v7. If Gerald’s message is 10 bytes long, he will require 4 transmissions to send the message over this path (3 + 3 + 3 + 1).

1. 1. [4 marks] Gerald has noticed some suspicious activity on the network, and thinks that Song might be trying to intercept the message! Only the first l∗ bytes of the message contain the confidential answers, and the rest is full of skull emojis. A subset E∗ ⊆ E of the network links are encrypted, so Gerald can only send the confidential bytes over these links. Fortunately, he knows that there is at least one path v1 → · · · → vn where all links in the path are encrypted. The skull emojis can be sent over any links.

      If the blue edges below represent the encrypted edges

      E∗ = {(v1, v2), (v1, v4), (v2, v5), (v4, v6), (v4, v7), (v6, v7)},

      and Gerald has a message of 10 bytes where the first 3 are confidential, he could send the first 4 bytes along the path v1 → v4 → v7 in 2 transmissions, then the remaining 6 bytes along the path v1 → v3 → v6 → v7 in another 2 transmissions, for 4 transmissions in total. This ensures that all confidential bytes are only sent over encrypted links.

      2

      v2           4          v5

      4

      2

      v1             2            v4             2            v7

      5

      4

      3

      v3           3            v6

      Design an O(m log n) algorithm which determines the smallest number of transmissions required to send Blake the message without Song intercepting any of the confidential material.

   2. [6 marks] Before sending the message, Gerald remembered that Song is an expert cyber- criminal who can break the encryption and intercept the entire message if the same byte travels over more than one unencrypted link, even if it’s just a skull emoji!

Using the above example, Gerald could send the first 3 bytes along the path v1 → v4 → v7, then the remaining bytes along the path v1 → v2 → v5 → v7, as this path includes only one unencrypted link. He can not use the path v v v v , as this includes more than one unencrypted

Figure 1: Gerald, Blake and Song are commonly used characters to illustrate network users

(image from Wikipedia).