Algorithms 3927 Assignment 4 The University of Sydney 2019 Semester 1 School of Computer Science
This assignment is for COMP3927 students only.
Problem 1: 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: [30 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: [30 marks]
Prove the network flow problem you have described is equivalent to the grid mining problem.
Task 3: [10 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.
Problem 2: Description
In the weighted global min cut problem, we are given an n-vertex undirected graph G = (V,E) and a non-negative weight w(u,v) for each edge (u,v) ∈ E. The weight of a cut (A,B) is the total weight of edges crossing the cut; more precisely, the weight of (A, B) is
w(u, v). (u,v)∈E:u∈A,v∈B
The goal is to find a cut (A, B) of least weight.
In class, we showed that if the weights are 1, then the randomized contraction algorithm finds a min
cut with probability at least 1/n. The goal of this task is to show that applying this algorithm directly 2
to weighted graphs is a bad idea.
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.
Task 4: [30 marks]
Your task is to give an example of an n-vertex graph G = (V,E) with edge weights w(u,v) such that the probability that the randomized contraction algorithm finds a min-weight cut is at most c/2n, for some constant c.
Algorithm 1 Randomized contraction algorithm
1: 2:
3: 4: 5: 6:
7: 8: 9:
10: 11:
procedureRandomized-contraction(G=(V,E))
Initialize S(v) = {v} for each vertex v. ◃ S(v) keeps track of the vertices that have been
contracted into v.
Initialize G0 = G.
for i ← 1 to |V | − 2 do
v.
Choose an edge e = (u, v) of Gi−1 uniformly at random.
Let Gi be the graph resulting from the contraction of e, with a new vertex zuv replacing u and
Define S(zuv) to be the union of S(u) and S(v) end for
Let y and z be the two vertices of G|V |−2.
Return the cut (S(y), S(z)). end procedure
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.
• To facilitate anonymous grading, please do not write your name on your submission.
2