Program Analysis Term 1, 2016
Assessed Coursework 2
Due date: Submit to Engineering and Informatics School Office by 4pm
on Wednesday 7th of December 2016.
Return date: Marked coursework will be available for collection from the Engineering and Informatics School Office on Monday 9th of Jan- uary 2017.
Assessment: Please answer all three questions. A total of 100 marks are available. Please note that credit will be given for partially correct answers. Submissions may be handwritten or produced with word processing software.
Avoiding misconduct If you do submit work that is not your own you must explicitly identify the source.
Program Analysis
1. Consider the following problem. Inputs: There are three inputs:
a sequence A = (a1,…,an) of n real numbers, a real number p and
a real number q.
Term 1, 2016
Output: The number of elements of A that are greater than or equal to p and less than or equal to q.
- (a) Givearecursivealgorithm,NumberInRange(A,p,q,i),thatsolves this problem.
Note that the parameter i is needed to record which part of the sequence A is being considered for a given recursive call. So NumberInRange(A, p, q, i) returns the number of values within the specified range (i.e. greater than or equal to p and less than or equal to q) from the subsequence (a1, . . . , ai).
[10 marks]
- (b) Express the running time of the algorithm you have given in answer to Question 1a using recurrences. [10 marks]
- (c) Solve the recurrences you have given in answer to Question 1b to find the running time of the algorithm. [10 marks]
Program Analysis Term 1, 2016 2. This question concerns the BellmanFord algorithm which is repro-
duced here.
BellmanFord(G, w, s, t):
(1) (2) (3) (4) (5) (6) (7) (8) (9)
B(0,t)←0 B(0,v)←∞foreachv∈V −{t} fori←1to|V|−1
for each v ∈ V
B(i, v) ← B(i − 1, v) for each (v, u) ∈ E
if B(i, v) > w(v, u) + B(i − 1, u) then B(i, v) ← w(v, u) + B(i − 1, u)
return B(|V | − 1, s)
(a) Show the result of running the Bellman Ford algorithm on the graph G1 shown below where the parameter s is v1 and the pa- rameter t is v4.
You need to do two things:
• complete the table B below; and
• concisely explain how each value in the table has been cal- culated. Do not be overly verbose.
G1: v3
2 -7 2
v1 v4 v5 65
-1 -5 -6
v2
Program Analysis Term 1, 2016
B:
[5 marks]
- (b) Is the asymptotic running time of the BellmanFord algorithm affected by the number of times that the condition in the if state- ment on line (7) is true? Explain your answer.
[5 marks]
- (c) Explain what would happen if the BellmanFord algorithm was given a graph with a negatively weighted cycle.
[5 marks]
- (d) Without changing the structure (i.e. the vertices and edges) of the graph G1 shown above, make minimal changes to the edge weights so that the BellmanFord algorithm produces a ta- ble where row 3 is different from row 2, but the same as row 4.
[5 marks]
- (e) Modify the BellmanFord algorithm so that it terminates after i iterations of the for loop on line (3) if it is determined that B(i, v) = B(i − 1, v) for all v ∈ V .
Note that when you could break out of a loop it is appropriate to use a while loop rather than a for loop.
[5 marks]
- (f) Give a full characterisation of the asymptotic running time of the algorithm that you have given in answer to Question 2e.
[5 marks]
|
v1 |
v2 |
v3 |
v4 |
v5 |
|
|
0 |
|||||
|
1 |
|||||
|
2 |
|||||
|
3 |
|||||
|
4 |
Program Analysis Term 1, 2016
(g) Consider the slightly modified Bellman Ford Algorithm shown below which operates on undirected graphs rather than directed graphs. Instead of the set of edges, E, being a set of pairs, it is a set of two elements sets. Hence, in line (6), rather than refer- ring to the directed edge (v, u), in this version we refer to the undirected edge { v, u }. To appreciate this distinction, note that (v, u) ̸= (u, v), whereas { v, u } = { u, v }.
BellmanFord(G, w, s, t):
(1) (2) (3) (4) (5) (6) (7) (8) (9)
B(0,t)←0 B(0,v)←∞foreachv∈V −{t} fori←1to|V|−1
for each v ∈ V
B(i, v) ← B(i − 1, v) for each {v, u} ∈ E
if B(i, v) > w(v, u) + B(i − 1, u) then B(i, v) ← w(v, u) + B(i − 1, u)
return B(|V | − 1, s)
Demonstrate that this algorithm does not work correctly on undi- rected graphs by considering the graph G2 below, which is a variant of graph G1 where all edges shown are undirected.
In order to do this, you should show that the algorithm does not find the correct solution when given G2 as input. As before, let parameter s be the vertex v1 and t be the vertex v4.
G2: v3
2 -7 2
v1 v4 v5 65
-1 -5 -6
v2
[5 marks]
Program Analysis Term 1, 2016 3. Consider the following instance of the bipartite matching problem.
- v1 v4
- v2 v5
- v3 v6
As explained in the lectures (Topic 10), the Ford-Fulkerson Network Flow algorithm can be used to solve the Bipartite Matching prob- lem. An instance of the Bipartite Matching problem is translated into an instance of the Network Flow problem which can then be solved with the Ford-Fulkerson algorithm. The solution that is produced by the Ford-Fulkerson algorithm is then transformed into a solution to the original instance of the Bipartite Matching problem.
For reference, here is the Ford-Fulkerson algorithm:
MaximumFlow(G, s, t, c):
- (1) let f(e) = 0 for all e ∈ E
- (2) let Gf be the residual graph built from G and f
- (3) while there is a path from s to t in Gf
- (4) letpbeasimplepathfromstotinGf
- (5) let x be residual capacity of bottleneck edge of p
- (6) f ← augment(G, f, p, x)
- (7) let Gf be residual graph built from G and f
- (8) return f
Program Analysis Term 1, 2016
- (a) Show (by drawing the network) the instance of the Network Flow problem that would be produced from the above instance of the Partite Matching problem.
Each edge should be annotated with the current flow (initially zero) and the edge’s capacity. In general, a flow of x along an edge with capacity y should be shown with the edge label x/y. So the following edge from u to v has a flow rate of 4 and a capacity of 9.
u 4/9 v
[5 marks]
- (b) Suppose that the Ford-Fulkerson algorithm is given your an- swer to Question 3a as input. Show the residual graph that would be produced in line (2).
In drawing a residual graph, a compact way to show a forward edge with capacity x and a backward edge with capacity y, is to annotate the original edge with −→x ; ←−y . So the following edge from u to v is a compact representation of two edges in the residual graph: a forward edge with capacity of 5 as well as a backward edge with capacity of 3.−→5 ; ←−3 uv
[5 marks]
- (c) Suppose that on the first iteration of the while loop, the path p that is selected on line (4) is the source to sink path that includes the forward edge from v1 to v4. Let f be the augmented flow based on this path (see line 6). Show both the network with flow f , as well as the residual graph Gf that would be produced in line (8).
[10 marks]
- (d) ContinuingfromyouranswertoQuestion3c,runtheFord-Fulkerson algorithm through to completion to find the maximum flow possible. You should show each of the steps you take. In particular, for each iteration of the while loop on line (3), show the residual graph Gf ,
Program Analysis Term 1, 2016
the selected path p, identify x, the residual capacity of the bottleneck edge of p, and the network’s flow that results from augmenting the flow based on path p.
Note that there can be several different simple paths from the source to the sink in a residual graph. You are free to choose any of the avail- able options. [10 marks]
(e) Specify the solution that is produced for the original instance of the Bipartite Graph problem, based on the solution you have produced in answer to Question 3d. [5 marks]