Due: 3 November 2019 at 11.59pm
Submit your assignment via Canvas. Submission must be in pdf format, and cannot be handwritten.
COMP9007 Algorithms – Assignment 3
As a first step go to the last page and read the section: Advice on how to do the home work.
Problem 1
Consider the flow network depicted below. The x/y values are x = flow and y = capacity.
a) Trace the Ford-Fulkerson algorithm on this network. Draw the residual graph and the augmenting path
in each iteration.
b) Prove that the flow you obtained from tracing the algorithm is a maximum flow.
(10 marks) (10 marks)
a 0/13
3/14
b
3/7
Problem 2
st
0/2 3/3
3/5
0/10
c
3/6
d
A social network is often represented as an undirected graph, G = (V, E) and |V | = n, where people within the network are represented by vertices and an edge exists in the graph between a pair of vertices (u, v ∈ V ) if u and v know one another (either as a friend or acquaintance). The analysis of the patterns formed within social networks is an interdisciplinary field which ranges from social psychology through to graph theory. Social networks analysis is also a valuable tool for targeted advertising. If an individual likes a product then it is more likely that their friends or acquaintances will also like the same product, compared to a randomly selected person from a sufficiently large social network.
It is due to this phenomena that you have been tasked with designing a survey for a new product which is currently under development. The aim of this survey is to maximise the diversity of the feedback. To achieve this goal the constraint which has been imposed on this survey is to ensure that no two people surveyed know one another or share a common friend or acquaintance. Your task is to check whether it is possible to conduct a survey with at least k participants where the imposed constraint is maintained. In addition, you want to be able to to find the set of participants of maximum size for the survey.
More formally the two problems which you wish to solve are:
• Diverse Survey Problem: given a social network G and an integer k, does there exist a set of participants of size at least k where no two participants included in the survey are connected to one another or are adjacent to a common node in the graph.
1
• Maximum Diverse Survey Problem: given a social network G, find the maximum size set of participants for the survey where no two participants included in the survey are connected to one another or are adjacent to a common node in the graph.
Your task is to answer three questions related to these problems:
a) Prove that the Diverse Survey Problem is in NP. (10 marks)
b) Prove that Independent Set ≤p Diverse Survey Problem. Note that both of these problems are decision problems. (10 marks)
c) Assume you have an implementation of the Diverse Survey Problem which you can use as a subrou- tine. Note that the subroutine takes as an input a graph and an integer and solves the decision problem and therefore only returns true or false. Design an algorithm which solves the Maximum Diverse Sur- vey Problem that makes at most a polynomial number of calls to the Diverse Survey Problem subroutine, and a polynomial amount of extra work (if needed). Make your algorithm as efficient as pos- sible. Your answer should include an explanation of the time complexity of the algorithm. In particular, how many calls to the subroutine does your algorithm require? (10 marks)
Problem 3
For each of the following problems decide if the proposed answer correctly solves the problem. If it does, then analyse the running time of the algorithm. If it does not, give a counterexample (an example demonstrating that the approach does not work). (10 marks per problem)
a) Problem: Paul was very happy with your help in figuring out the order in which he can take the courses he’s interested in. Now that he knows that he can take these courses, he wants to find out how many semesters it would take him to take all of them (he’s confident he’ll pass all of them on the first attempt). For simplicity, we assume that every course is offered every semester and an unlimited number of courses can be taken each semester, so once Paul has completed all prerequisites, he can immediately take the course.
Solution: We first construct the directed acyclic graph with a vertex for each course and a directed edge (u,v) if u is a prerequisite of v and we call the set of vertices that have an edge to v the neighborhood of v. The idea is to run depth first search on this graph and store for each vertex how many steps away its furthest vertex is. In other words, for each vertex v we store the number of semesters required if v is taken in the first semester. After computing this, we find the vertex whose furthest vertex is the most steps away.
Algorithm 1: Count-Semesters
1 2 3 4 5 6 7
1 2 3 4 5
Construct the DAG from the prerequisite information Mark all vertices as unvisited
Set Furthest[v] to 1 for all vertices foreachvertexv∈V do
if v is unvisited then Find-Furthest(v)
return the maximum value in Furthest Algorithm 2: Find-Furthest(v)
Mark v as visited
for each vertex u in the neighborhood of v do
if u is unvisited then Find-Furthest(u)
Furthest[v] = max{Furthest[v], Furthest[u] + 1} 2
b) Problem: We have a wired computer network consisting of a number of routers v1,…,vn, a server s,
and a high performance computing unit t. These are connected using m cables that can transmit data in
both directions. We want to transfer as much data from the server to the high performance computer as
we can. The problem is, the data we are processing is very large (but all of the same size) and it takes
a router a significant amount of time to receive the data and prepare it for retransmission. Because of
this, we want each router to only be on one path. How much data can we transmit at the same time?
Solution: We model this as a flow problem. The vertices of our graph are s, t, and for every router vi,
we introduce two vertices: vin and vout. We add a directed edge from vin to vout. We also add a directed ii ii
edge from vout to vin (and also from vout to vin) if there is an edge between them in the network. Finally, ij ji
we add an edge from s to every router it is connected to and we add an edge to t from every router it is connected to. Every edge has capacity 1. We run the Ford-Fulkerson algorithm to find the max flow in the network and return this as the solution.
c) Problem: We are bank robbers and we made it into the bank vault. Unfortunately, the bank has more valuables than we can carry. We want to make the most of our efforts and obtain the highest total value, while making sure that we can carry it to our getaway car. We see n items, each having a value vi and some effort ei to take with us. Our carrying capacity is C. We want to pick the items with total effort at most C that maximize the total value.
Solution: We are greedy, so we just grab the most valuable thing first. Afterwards we check how much more we can carry and grab the most valuable item of weight less than our remaining carrying capacity. We continue this process until none of the items fit in our remaining capacity. More formally, our algorithm looks like this:
Algorithm 3: Bank Robbers(A, C)
1 2 3 4 5 6 7
Sort all items in A in decreasing order of value (i.e., A[1] is the item of highest value) Solution = ∅
fori=0;i
Reviews
There are no reviews yet.