AlgorithmDesign Assignment4 s12024
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“AcademicDishonestyandPlagiarism”policies.
Asafirststepgotothelastpageandreadthesection: “Adviceonhowtodotheassignment”.
Important: ThisassignmentisforallCOMP3x27students. COMP3027studentsshoulddoProblems1and
2whileCOMP3927studentsshoulddoProblems1,2,and3.
Background. Wow! Go-karting sure was fun. However, you had an unfortunate encounter with
Truck-kunandfindyourselfisekai-edintoDune,ofallplaces. Luckily,you’reatleastamid-ranking
official in the Arrakis administration so your new life isn’t too bad. You get to work in plotting to
deposeyourrivalsinpower.
Problem 1. (40pointsforCOMP3027,30pointsforCOMP3927)
Oneofyourrivalsisanofficialmanagingspicemining. InthisversionofArrakis,spiceismined
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
andthey’llgoberserk,destroyingeverythingonArrakis.
Formally,theproblemisthatthere’sanundirectednetwork (V,E) of n nodes,whereeachundi-
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 ∑ w(u,v) is maximised, with the further condition that the number of S-T
u∈S,v∈T
edges (u,v) ∈ E (where u ∈ S,v ∈ T)iseven.
a) Definethedecisionversionofthisproblem.
b) ProvethatthisdecisionproblemisinNP.
c) ProvethatthisdecisionproblemisNP-Complete.
d) ConcludethattheoriginalsearchproblemisNP-Hard.
Problem 2. (60pointsforCOMP3027,COMP3927)
You’vesuccessfullyremovedyouroppositionandarenowthepipelinemanagerforArrakis. You
thinkthereisanewopportunityforefficiencybycombiningthespicedistributionnetworkandthe
waterdistributionnetwork. Ofcourse,youcan’ttransportbothwaterandspiceinthesamepipeline,
sothismightlimityourefficiencygains. Howmuchmoreefficiencycanwegainfromthischange?
Formally, we have a directed network (V,E) on n nodes, including two sources and one sink,
s 1,s 2,t ∈V. Eachdirectededge(u,v)hasacapacityc(u,v) ∈Z ≥0,andwehavetwoflows f,g :V×
V → Z ≥0. We have the usual flow conservation and capacity constraints for f and g individually,
withtheadditionalconstraintthatforeachedge,atleastoneof f(u,v)andg(u,v)is0. Furthermore,
for all vertices v ∈ V\{s ,s }, g(s ,v) = f(s ,v) = 0, i.e. s only supplies f-flow and s only
1 2 1 2 1 2
supplies g-flow. Finally, we want to maximise the combined flow into t, i.e. ∑ (f(v,t)+g(v,t))
v∈V
ismaximised.
a) Definethedecisionversionofthisproblem.
b) ProvethatthisdecisionproblemisinNP.
c) ProvethatthisdecisionproblemisNP-Complete. Hint: 3-SATmightgiveagoodreductionhere.
d) ConcludethattheoriginalsearchproblemisNP-Hard.
1
AlgorithmDesign Assignment4 s12024
Problem 3. (10points)(COMP3927only)
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
anyonewhocouldpossiblytakeover.) Comeupwithanalgorithmthatsavesyousomeeffort.
Formally, again we have a directed network (V,E) on n nodes, including two sources and one
sink, s 1,s 2,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. Weagainhavetheusualflowconservationandcapacityconstraintsfor f
and g individually, with the additional constraint that for each edge, at least one of f(u,v), g(u,v)
is0. Furthermore,forallvertices v ∈V\{s ,s }, g(s ,v) = f(s ,v) =0,i.e. s onlysupplies f-flow
1 2 1 2 1
and s onlysupplies g-flow. Maximisethecombinedflowinto t,i.e. ∑ (f(v,t)+g(v,t)).
2 v∈V
a) Developanalgorithmthatisa1/2-approximationtothisoptimisationproblem.
Hint: Don’toverthinkthis.
b) Proveitscorrectness.
c) Analyseitsrunningtime.
2
AlgorithmDesign Assignment4 s12024
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
yourname.
• Submitonlyyouranswerstothequestions. Donotcopythequestions.
• When asked to give a plain English description, describe your algorithm as you would to a
friendoverthephone,suchthatyoucompletelyandunambiguouslydescribeyouralgorithm,
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
canalsoincludepseudocode,butthisisoptional.
• Inparticular,whendesigninganalgorithmordatastructure,itmighthelpyou(andus)ifyou
briefly describe your general idea, and after that you might want to develop and elaborate on
details. Ifwedon’tsee/understandyourgeneralidea,wecannotgiveyoumarksforit.
• 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 indicates how well you understood
thequestion.
• 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
thannecessary(seecommentabove).
• Whengivinganswerstoquestions,alwaysprove/explain/motivateyouranswers.
• 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
mostefficientalgorithmsanddatastructures.
• Ifyouusefurtherresources(books,scientificpapers,theinternet,...) toformulateyouranswers,
then add references to your sources and explain it in your own words. Only citing a source
doesn’tshowyourunderstandingandwillthusgetyouveryfew(ifany)marks. Copyingfrom
anysourcewithoutreferenceisconsideredplagiarism.
3