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 :
{
δ(x, y) =
(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.
(c) Describe a procedure for recovering the alignment that gives rise to the op- timal solution found by the algorithm.
(d) How efficient is this procedure?
0 ifx=y
1 otherwise
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.
(b) Describe a procedure for recovering the path that gives rise to the optimal solution found by the algorithm.
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
(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.