Algorithms 3027 Assignment 4 The University of Sydney 2019 Semester 1 School of Computer Science
This assignment is for COMP3027 students only.
Description
You have been put in charge of running mining operations in the underground city of Algo-Rithm. Your mine consists of an a × a square grid, where each grid square is open space, lava, a vein of gold ore or a rare vein of diamond. A miner may stand on an open grid square, but occupies the whole square, so that no two miners can occupy the same square. A miner who is standing next to a vein can mine one unit of gold or diamond (depending on the vein type) from it; up to one miner can mine from a gold vein and up to two can mine from a diamond vein.
Your task is to determine, based on the layout of your mine, the minimum number of miners to hire such that the mine outputs as many units as possible, but no miners are left with nothing to do. For each miner you hire you must describe where they should stand and which vein they should mine.
You may assume that the mine layout is given to you as an a × a array P with
P[i][j] =
open lava gold diamond
if grid square (i, j) is open
if grid square (i, j) is lava
if grid square (i,j) is gold ore if grid square (i, j) is diamond
You may assume there are ko open spaces, kb lava spaces, kg gold spaces and kd diamond spaces. Refer to the number of miners you employ as M.
Task 1: [40 marks]
Formulate the grid mining problem as a network flow problem and describe how the solution can be derived from the max flow on that network.
Task 2: [40 marks]
Prove the network flow problem you have described is equivalent to the grid mining problem.
Task 3: [20 marks]
Prove the time complexity of your solution to the grid mining problem. Don’t forget to consider:
• How long does it take to transform the input into a network flow problem?
• How long does it take to solve the network flow problem?
• How long does it take to transform the network flow solution into a solution to the grid mining problem?
Specify the time complexity in terms of the input to the grid mining problem.
Submission details
• Submission deadline is Wednesday 15th May, at 23:59. Late submissions without special consideration will be subject to the penalties specified in the first lecture (5% per day; 0 marks after 10 days late).
• Submit your answers to all tasks as a single document to Canvas. Your work must be typed (no images of text, although you can use diagrams if you think it helps.) Please try to be reasonably concise (up to 4 pages of A4 for 3027 and 6 pages of A4 for 3927).
• Your report will be subject to automatic and manual plagiarism detection systems. Remember, it’s acceptable to discuss high level ideas with your peers, but you should not share the detail of your work, such as parts as the precise algorithms, examples, proofs, writing, or code.
1
m
m
m
m
m
m
m
m
Figure 1: Left a grid mining instance and right a solution using 8 miners producing a total output of 8 units. Yellow circles represent gold spaces, black diamonds represent diamond spaces.
• To facilitate anonymous grading, please do not write your name on your submission.
2