Algorithm Design
Assignment 4
s1 2024
This assignment is due on May 15 and should be submitted on Gradescope. All submitted work must be done individually without consulting someone else’s solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.
As a first step go to the last page and read the section: “Advice on how to do the assignment” .
Important: This assignment is for all COMP3x27 students. COMP3027 students should do Problems 1 and 2 while COMP3927 students should do Problems 1, 2, and 3.
Background. Wow! Go-karting sure was fun. However, you had an unfortunate encounter with Truck-kun and find yourself isekai-ed into Dune, of all places. Luckily, you’re at least a mid-ranking official in the Arrakis administration so your new life isn’t too bad. You get to work in plotting to depose your rivals in power.
Problem 1. (40 points for COMP3027, 30 points for COMP3927)
One of your rivals is an official managing spice mining. In this version of Arrakis, spice is mined from deposits and transported in pipelines. To get rid of your rival and take over the area under their control, you’ve obtained control of a space laser and want to find out how much damage we can possibly do to their pipelines. However, the controls of the laser are a bit hard to use, and you can only program it to draw a loop around nodes in the transport network. Furthermore, the laser manual warns you that if you blow up an odd number of pipelines, this will anger the sandworms and they’ll go berserk, destroying everything on Arrakis.
Formally, the problem is that there’s an undirected network (V, E) of n nodes, where each undi- rected edge has an integer weight w (u, v) = w (v, u) > 0 (and if there is no edge between u, v then w (u, v) = 0). We want to choose a cut such that the nodes are divided into sets S, T, where the capacity of the cut Σu ∈S,v ∈Tw(u, v) is maximised, with the further condition that the number of S-T edges (u, v) ∈ E (where u ∈ S, v ∈ T) is even.
a) Define the decision version of this problem.
b) Prove that this decision problem is in NP.
c) Prove that this decision problem is NP-Complete.
d) Conclude that the original search problem is NP-Hard.
Problem 2. (60 points for COMP3027, COMP3927)
You’ve successfully removed your opposition and are now the pipeline manager for Arrakis. You think there is a new opportunity for efficiency by combining the spice distribution network and the water distribution network. Of course, you can’t transport both water and spice in the same pipeline, so this might limit your efficiency gains. How much more efficiency can we gain from this change?
Formally, we have a directed network (V, E) on n nodes, including two sources and one sink, s1, s2, t ∈ V. Each directed edge (u, v) has a capacity c (u, v) ∈ Z ≥0, and we have two flows f , g : V × V → Z ≥0. We have the usual flow conservation and capacity constraints for f and g individually, with the additional constraint that for each edge, at least one off(u, v) and g(u, v) is 0. Furthermore, for all vertices v ∈ V \ {s1, s2}, g(s1, v) = f(s2, v) = 0, i.e. s1 only supplies f-flow and s2 only supplies g-flow. Finally, we want to maximise the combined flow into t, i.e. Σv ∈V(f(v, t) + g(v, t)) is maximised.
a) Define the decision version of this problem.
b) Prove that this decision problem is in NP.
c) Prove that this decision problem is NP-Complete. Hint: 3-SAT might give a good reduction here. d) Conclude that the original search problem is NP-Hard.
Problem 3. (10 points) (COMP3927 only)
NP-hardness can’t stop you! If only half the maximum possible flow gets through at any time, that’s good enough for you. (You don’t need to be the best at your job, you only need to remove anyone who could possibly take over.) Come up with an algorithm that saves you some effort.
Formally, again we have a directed network (V, E) on n nodes, including two sources and one sink, s1, s2, t ∈ V. Each directed edge (u, v) still has a capacity c (u, v) ∈ Z ≥0, and we still have two flows f , g : V × V → Z ≥0. We again have the usual flow conservation and capacity constraints for f and g individually, with the additional constraint that for each edge, at least one off(u, v), g(u, v) is 0. Furthermore, for all vertices v ∈ V \ {s1, s2}, g(s1, v) = f(s2, v) = 0, i.e. s1 only supplies f-flow and s2 only supplies g-flow. Maximise the combined flow into t, i.e. Σv ∈V(f(v, t) + g(v, t)).
a) Develop an algorithm that is a 1/2-approximation to this optimisation problem.
Hint: Don’t overthink this.
b) Prove its correctness.
c) Analyse its running time.
Advice on how to do the assignment
• Assignments should be typed and submitted as pdf (no pdf containing text as images, no handwriting).
• Start by typing your student ID at the top of the first page of your submission. Do not type your name.
• Submit only your answers to the questions. Do not copy the questions.
• When asked to give a plain English description, describe your algorithm as you would to a friend over the phone, such that you completely and unambiguously describe your algorithm, including all the important (i.e., non-trivial) details. It often helps to give a very short (1-2 sentence) description of the overall idea, then to describe each step in detail. At the end you can also include pseudocode, but this is optional.
• In particular, when designing an algorithm or data structure, it might help you (and us) if you briefly describe your general idea, and after that you might want to develop and elaborate on details. If we don’t see/understand your general idea, we cannot give you marks for it.
• Be careful with giving multiple or alternative answers. If you give multiple answers, then we will give you marks only for "your worst answer", as this indicateshow well you understood the question.
• Some of the questions are very easy (with the help of the slides or book). You can use the material presented in the lecture or book without proving it. You do not need to write more than necessary (see comment above).
• When giving answers to questions, always prove/explain/motivate your answers.
• When giving an algorithm as an answer, the algorithm does not have to be given as (pseudo- )code.
• If you do give (pseudo-)code, then you still have to explain your code and your ideas in plain English.
• Unless otherwise stated, we always ask about worst-case analysis, worst case running times, etc.
• As done in the lecture, and as it is typical for an algorithms course, we are interested in the most efficient algorithms and data structures.
• If you use further resources (books, scientific papers, the internet,...) to formulate your answers, then add references to your sources and explain it in your own words. Only citing a source doesn’t show your understanding and will thus get you very few (if any) marks. Copying from any source without reference is considered plagiarism.