Program Analysis Problem Sheet 10
1. Consider the SequenceAlignment algorithm given below. SequenceAlignment(X, Y ):
let B(i, 0) ← i · γ for each 0 ≤ i ≤ n let B(0, j) ← j · γ for each 1 ≤ j ≤ m for i ← 1 to n
forj ←1tom
B(i, j) ← min[ δ(xi, yj ) + B(i − 1, j − 1),
γ + B(i, j − 1), γ + B(i − 1, j) ]
Term 1, 2015
(a) Apply the algorithm to find the optimal solution to the following problem instance.
A = (i,n,f,o,r,m,a,t,i,o,n) B = (o,n, ,f,a,r,m, ,s,t,a,t,i,o,n)
where γ = 1 and for all characters x and y :
Model Answer:
{
δ(x, y) =
0 ifx=y
1 otherwise
i
n
f
o
r
m
a
t
i
o
n
0
1
2
3
4
5
6
7
8
9
10
11
o
1
1
2
3
3
4
5
6
7
8
8
9
n
2
2
1
2
3
4
5
6
7
8
9
8
3
3
2
2
3
4
5
6
7
8
9
9
f
4
4
3
2
3
4
5
6
7
8
9
10
a
5
5
4
3
3
4
5
5
6
8
9
10
r
6
6
5
4
4
3
4
5
6
7
8
9
m
7
7
6
5
5
4
3
4
5
6
8
9
8
8
7
6
6
5
4
4
5
6
7
8
s
9
9
8
7
7
6
5
5
5
6
7
8
t
10
10
9
8
8
7
6
6
5
6
7
8
a
11
11
10
9
9
8
7
6
6
6
7
8
t
12
12
11
10
10
9
8
7
6
7
7
8
i
13
12
12
11
11
10
9
8
7
6
7
8
o
14
13
13
12
12
11
10
9
8
7
6
7
n
15
14
14
13
13
12
11
10
9
8
7
6
(b) Modify the above algorithm so that sufficient information is stored (in a sec- ond table) in order that the optimal solution (optimal alignment) can be effectively recovered. It should be possible to recover one element of the alignment with each probe of the table.
Program Analysis
Model Answer:
SequenceAlignment(X, Y ):
let B(i, 0) ← i · γ for each 0 ≤ i ≤ n let C(i, 0) ← (0, 0) for each 0 ≤ i ≤ n letB(0,j)←(0,0)foreach1≤j ≤m for i ← 1 to n
forj ←1tom
if δ(xi, yj ) + B(i − 1, j − 1) > γ + B(i, j − 1)
if δ(xi, yj ) + B(i − 1, j − 1) > γ + B(i − 1, j) B(i,j) ← δ(xi,yj) + B(i − 1,j − 1) C(i,j) ← (i,j)
else
B(i, j) ← γ + B(i − 1, j)
C(i, j) ← C(i − 1, j) else
if B(i, j − 1) > B(i − 1, j) B(i, j) ← γ + B(i, j − 1) C(i, j) ← C(i, j − 1)
else
B(i, j) ← γ + B(i − 1, j) C(i, j) ← C(i − 1, j)
Term 1, 2015
(c) Describe a procedure for recovering the alignment that gives rise to the op- timal solution found by the algorithm.
Model Answer:
GetSolution(C, i, j) :
(p,q) ← C(i,j) if p = q = 0
return ∅ else
return (i, j) ∪ GetSolution(C, p − 1, q − 1) with an initial call of GetSolution(C, n, m).
(d) How efficient is this procedure?
Model Answer: This algorithm has running time of Θ(k) where k is the number of pairs in the optimal alignment. The reason for this this is that ex- actly one pair of the solution is found at each level of recursion, and finding this pair takes constant time.
Program Analysis
2. Consider the BellmanFord algorithm given below. BellmanFord(G, w, s, t):
let B(0, t) ← 0 letB(0,v)←∞foreachv∈V −{t} for i ← 1 to n − 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)
Term 1, 2015
(a) Modify the above algorithm so that sufficient information is stored (in a sec- ond table) in order that the optimal solution (path) can be effectively recov- ered. It should be possible to recover one edge of the path with each probe of the table.
Model Answer:
BellmanFord(G, w, s, t):
let B(0, t) ← 0
let C(0, t) ← (0, t) letB(0,v)←∞foreachv∈V −{t} for i ← 1 to n − 1
for each v ∈ V
B(i,v) ← B(i − 1,v) C(i, v) ← C(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) C(i,v) ← (i,u)
(b) Describe a procedure for recovering the path that gives rise to the optimal solution found by the algorithm.
Model Answer:
GetSolution(C, i, v) :
(j,u) ← C(i,v) if (j,u) = (0,t)
return (t) else
return result of inserting v to the front of GetSolution(C, j − 1, u) with an initial call of GetSolution(C, n − 1, s).
Program Analysis Term 1, 2015
3. Suppose G = (V, E) is a directed graph where v1, . . . , vn is an enumeration of the vertices in the graph. In other words, we have determined a fixed ordering for the vertices so that when we say the ith vertex for some i ∈ {1,…,n} we are consistently identifying a particular vertex. The graph G is an ordered graph if it has the following features.
• Eachedgegoesfromavertexwithalowerindex(intheaboveenumeration) to a vertex with a higher index. In other words, directed edge has the form (vi,vj) with i < j.
• All vertices other than vn have at least one outgoing edge. In other words, for all vertices vi, i = 1,2,...,n − 1, the graph contains at least one edge (vi,vj).
Recall that length of a path is defined as the number of edges in the path. For this question you need to solve the following problem.
Given some ordered graph G, find the length of the longest of the paths that begins at v1 and ends at vn.
For example, the solution for the following ordered graph is 3: the longest path from v1 to vn has the edges (v1, v2), (v2, v4) and (v4, v5).
v1 v2 v3 v4 v5
(a) Explain why the algorithm below does not correctly solve the above prob- lem. To do this give an illustration of an ordered graph that the algorithm would produce the wrong answer for.
set u = v1
set len = 0
while there is an edge out of the node u
choose the edge (u, vj ) such that j is as small as possible u ← vj
len ← len+1
return len
Model Answer: The graph on nodes v1, . . . , v5 with edges (v1, v2), (v1, v3), (v2, v5), (v3, v4) and (v4, v5) is such an example. The algorithm will return 2 corresponding to the path of edges (v1, v2) and (v2, v5), while the optimum is 3 using the path (v1, v3), (v3, v4), (v4, v5).
Program Analysis Term 1, 2015 (b) Give an efficient dynamic programming algorithm that takes as input an
ordered graph G, returning the length of the longest path from v1 to vn. Model Answer: Use B[i] to hold the length of the longest path from v1 to
vi. We use the value −∞ when there is no path from v1 to vi. B[i] can be defined as follows.
B[i]=
0 if i = 1
max {1+B[j]} ifthereissome(vj,vi)∈E
(vj,vi)∈E
−∞ otherwise
The algorithm is as follows.
B[1] ← 0
for i ← 2 to n
B[i] ← −∞
for each (vj,vi) ∈ E
if B[i] < 1 + B[j] then B[i] ← 1 + B[j]
return B[n]