Functional programming, design and analysis of algorithms (A10097W1)

This is the 13 June 2017 preliminary examination. Questions 1–4 concern functional programming; Questions 5–8 concern algorithm design and analysis of algorithms. All 35 printed subparts are answered. Source paper: released examination archive, member a10097w1-1.pdf.

The Haskell definitions use separate question namespaces. For Question 1, hide the locally defined names with import Prelude hiding ((.), zipWith, uncurry); for Question 4 use import Prelude hiding (scanl). Alternative solve definitions are alternatives, not simultaneous duplicate declarations. Assume finite total puzzle inputs; infinite streams and partial values are treated explicitly where relevant. Operation counts separate numeric bit costs from list and comparison steps.^[ref]

Table of contents
- 1 Functional programming, design and analysis of algorithms
  - a 1
    - Solution a
  - b 1
    - Solution b
  - c 1
    - Solution c
  - d 1
    - Solution d
- 2 Functional programming, design and analysis of algorithms
  - a 2
    - Solution a
  - b 2
    - Solution b
  - c 2
    - Solution c
  - d 2
    - Solution d
  - e 2
    - Solution e
- 3 Functional programming, design and analysis of algorithms
  - a 3
    - Solution a
  - b 3
    - Solution b
  - c 3
    - Solution c
  - d 3
    - Solution d
  - e 3
    - Solution e
- 4 Functional programming, design and analysis of algorithms
  - a 4
    - Solution a
  - b 4
    - Solution b
  - c 4
    - Solution c
  - d 4
    - Solution d
- 5 Functional programming, design and analysis of algorithms
  - a 5
    - Solution a
  - b 5
    - Solution b
  - c 5
    - Solution c
- 6 Functional programming, design and analysis of algorithms
  - a 6
    - Solution a
  - b 6
    - Solution b
  - c 6
    - Solution c
  - d 6
    - Solution d
- 7 Functional programming, design and analysis of algorithms
  - a 7
    - Solution a
  - b 7
    - Solution b
  - c 7
    - Solution c
  - d 7
    - Solution d
  - e 7
    - Solution e
- 8 Functional programming, design and analysis of algorithms
  - a 8
    - Solution a
  - b 8
    - Solution b
  - c 8
    - Solution c
  - d 8
    - Solution d
  - e 8
    - Solution e

1

 0  0

a

 0  0

Solution

 0  0

The most general polymorphic type signatures and definitions are:

infixr 9 .

(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) x = f (g x)

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
zipWith _ _ _ = []

uncurry :: (a -> b -> c) -> (a,b) -> c
uncurry f (x,y) = f x y

Function composition passes the result of the second function into the first. zipWith combines corresponding list elements and stops when either list ends. Uncurrying converts a function taking two successive arguments into one taking a pair. None of these operations needs a numeric or ordering constraint.

b

 0  0

Solution

 0  0

The completed identities are:

filter p . map f = map f . filter (p . f)

filter p . concat = concat . map (filter p)

zipWith f = (map (uncurry f) .) . zip

The first tests the predicate after the mapped function; the second filters each inner list. In the third, zip is curried: after one argument it still returns a function of a second list. The operator section (map (uncurry f) .) composes with that returned function. Applying both sides to xs and ys gives map (uncurry f) (zip xs ys). Omitting the section's extra composition level would not type-check.

c

 0  0

Solution

 0  0

Generate each row of Pascal's triangle from its predecessor, padding at opposite ends before adding corresponding entries:

pascal :: Num a => [[a]]
pascal = iterate next [1]
  where
    next :: Num a => [a] -> [a]
    next row = zipWith (+) (0:row) (row ++ [0])

The boundary sums are the old endpoint plus zero, and the interior sums satisfy Pascal's rule. Induction on the iteration number therefore gives the rows of binomial coefficients. The outer lazy list is infinite, with each finite row available on demand. Instantiate a as Integer for exact arbitrarily large entries; bounded machine integers eventually overflow.

d

 0  0

Solution

 0  0

Application binds more tightly than function composition, and (.) associates to the right. Let

g :: a -> b -> c

Then y :: a and g y :: b -> c. To compose to its left, h x must have type c -> a, so x :: d and h :: d -> c -> a. The outer occurrence of g receives that a, producing a function of type b -> c. Consequently g . h x . g y has type b -> b -> c, and the principal type is f :: (a -> b -> c) -> (d -> c -> a) -> d -> a -> b -> b -> c. No Haskell type class constraint is introduced.

2

 0  0

a

 0  0

Solution

 0  0

Compare the two heads, emitting one copy of a tie and advancing both inputs in that case:

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge xs@(x:xt) ys@(y:yt)
  | x < y     = x : merge xt ys
  | x > y     = y : merge xs yt
  | otherwise = x : merge xt yt

The emitted head is the smallest remaining value, so induction preserves strict order and removes duplicates. The extra empty-input cases also make the definition useful on finite lists.

There is a mathematical qualification to the unrestricted infinite-input claim: the union must be enumerable in this order. If one input increases to one from below and the other starts at two, no finite output position can contain two. Locally finite sorted-stream merge excludes this obstruction, and applies to the positive integer streams needed below.

b

 0  0

Solution

 0  0

Tie the three scaled streams back to the same shared lazy list:

hamming :: [Integer]
hamming = 1 : merge (map (2*) hamming)
                    (merge (map (3*) hamming) (map (5*) hamming))

The resulting values are precisely the Hamming numbers

2^{i} 3^{j} 5^{k}

for nonnegative integers

i, j, k

. Every noninitial value has a smaller predecessor obtained by removing a factor, so the recursive demand can be supplied from earlier cells. This is the productivity argument for a sorted multiplicative closure stream. The merge algorithm removes duplicate representations such as

2 \cdot 3 = 3 \cdot 2

, retaining strict order and every generated value.

c

 0  0

Solution

 0  0

The first six shared values are [1,2,3,4,5,6]. At the logical merge frontier after emitting six, the streams have these consumed prefixes and next candidates:

Stream	Consumed values	Next candidate	Shared source cell
$2 \times$	$2, 4, 6$	$8$	fourth cell, value $4$
$3 \times$	$3, 6$	$9$	third cell, value $3$
$5 \times$	$5$	$10$	second cell, value $2$

Each row points into the same underlying lazy list, rather than recomputing an independent copy. The inner merge supplies the union of the last two rows, and the outer merge combines it with the first. Equal candidates at six advance both supplying streams. These next candidates describe the logical frontier: a demand such as take 6 hamming need not already have evaluated their numeric values.

Figure 1.
Shared Hamming-number stream after six outputs
. The three multiplier streams read earlier cells of one shared list. The pending values 8, 9 and 10 are logical next candidates, not a claim that take 6 forces them. **Details**.

d

 0  0

Solution

 0  0

The cost is $Θ (n)$ arithmetic and comparison operations under shared lazy evaluation and unit-cost operations on the numeric values. There are only three mapped streams and two merge nodes. Before the first

n

output cells are produced, each node advances at most

n + O (1)

input positions; each advance does a bounded number of operations. Producing the

n

output cells also gives an

Ω (n)

lower bound.

This is stream sharing in Hamming-number construction. It relies on sharing the recursive list cells, and is not a bound on bit operations: multiplying or comparing arbitrarily large Integer values costs more as their representations grow.

e

 0  0

Solution

 0  0

For exact ordered numbers, first discard multipliers equal to one and reject those below one:

hamming' :: (Ord a, Num a) => [a] -> [a]
hamming' as
  | any (<1) as = error "multipliers below one violate the ordered contract"
  | otherwise  = hs
  where
    bs = filter (>1) as
    hs = 1 : case bs of
               [] -> []
               _  -> foldr1 merge [map (a*) hs | a <- bs]

The type signature has exactly the numeric and ordering constraints used by the definition. For a finite nonempty collection of multipliers greater than one, this is the same sorted multiplicative closure stream construction as before, merging one scaled copy per multiplier. It is infinite and strictly increasing; local finiteness below any bound and the smaller-predecessor argument prove completeness and productivity. In particular, [2,3,5] reproduces hamming.

The literal contract for arbitrary positive multipliers is impossible. A multiplier strictly between zero and one would require a value smaller than the initial one; an empty list or the list [1] generates only one value. The definition returns the finite closure [1] in those degenerate cases. A multiplier equal to one adds no mathematical values and would introduce an unnecessary circular merge demand if left in the feedback streams. The order and growth proof assumes exact arithmetic with the usual laws; the broad numeric type alone cannot prevent floating-point rounding or bounded overflow.

3

 0  0

a

 0  0

Solution

 0  0

Using only list comprehensions:

type Matrix a = [[a]]
type Grid = Matrix Int

choicesComp :: Grid -> Matrix [Int]
choicesComp rows =
  [[[d | d <- [1..9], n == 0 || d == n] | n <- row] | row <- rows]

The input contract restricts each cell to zero or a digit from one to nine. A definition using standard list functions is:

choicesMap :: Grid -> Matrix [Int]
choicesMap = map (map choice)
  where
    choice :: Int -> [Int]
    choice 0 = [1..9]
    choice n = [n]

choices :: Grid -> Matrix [Int]
choices = choicesMap

Both preserve the row structure and construct the initial constraint domains of the Sudoku problem. The alternative names let both definitions coexist; either can supply choices.

b

 0  0

Solution

 0  0

The recursive Cartesian product is:

cpRec :: [[a]] -> [[a]]
cpRec [] = [[]]
cpRec (xs:xss) = [x:ys | x <- xs, ys <- cpRec xss]

The corresponding right fold is:

cpFold :: [[a]] -> [[a]]
cpFold = foldr step [[]]
  where
    step :: [a] -> [[a]] -> [[a]]
    step xs acc = [x:ys | x <- xs, ys <- acc]

cp :: [[a]] -> [[a]]
cp = cpRec

The base [[]] is essential: there is one way to choose from no factors, namely the empty selection. For a nonempty outer list, choose its first coordinate and prepend it to each selection from the remaining factors. This also proves equality with the right fold by structural induction. An empty factor produces no selections.

c

 0  0

Solution

 0  0

First enumerate each possible row, then choose one row from each row's alternatives:

expand :: Matrix [a] -> [Matrix a]
expand = cp . map cp

The inner Cartesian product converts one row of cell choices into its possible rows; the outer product combines those rows into whole matrices. Every assignment is represented exactly once when each cell's alternatives are distinct. Empty cell domains yield no grids, and an empty matrix yields the singleton list containing the empty matrix.

d

 0  0

Solution

 0  0

Enumerate assignments and retain exactly the valid completions:

solve :: Grid -> [Grid]
solve = filter complete . expand . choices

With

x

blank cells and all other entries fixed, the unpruned Cartesian product has $9^{x}$ candidate grids. Testing complete enforces every row, column and box condition. This is the size of the full candidate search; lazy evaluation can stop earlier if the caller demands only an initial portion of the solution list.

e

 0  0

Solution

 0  0

Prune until a fixed point before enumerating the surviving domains:

stable :: Eq a => (a -> a) -> a -> a
stable f x = let y = f x
             in if y == x then x else stable f y

solve :: Grid -> [Grid]
solve = filter complete . expand . stable prune . choices

New singleton cells can make a later pruning pass effective even if one pass has already run. Under the supplied deletion-only, solution-preserving contract, fixed-point pruning of finite constraint domains terminates: every changed pass strictly decreases the total number of candidates, initially at most

81 \cdot 9 = 729

. No valid solution is removed. An empty domain causes expand to return no candidates; a fixed point with unresolved alternatives still needs enumeration and the final complete test.

4

 0  0

a

 0  0

Solution

 0  0

Separate the empty prefix from the prefixes beginning with the first element:

inits :: [a] -> [[a]]
inits [] = [[]]
inits (x:xs) = [] : map (x:) (inits xs)

Every nonempty list prefix begins with x and continues with a prefix of xs. Thus the recursive order is increasing prefix length, beginning with length zero. Lazy evaluation can also expose every finite prefix of a productive infinite input.

b

 0  0

Solution

 0  0

The most general type signature is scanl :: (b -> a -> b) -> b -> [a] -> [b]. The left fold step consumes an accumulator of type b and an input of type a, returning the next accumulator. A left scan retains all these accumulator values, including the initial one.

c

 0  0

Solution

 0  0

Use map k (u:us) = k u : map k us, list-map fusion, and the left fold equation

foldl f e (x:ys) = foldl f (f e x) ys

For the empty list, the prefix definition immediately gives scanl f e [] = [e]. For a nonempty list, calculate:

scanl f e (x:xs)
  = map (foldl f e) ([] : map (x:) (inits xs))
  = e : map ((foldl f e) . (x:)) (inits xs)
  = e : map (foldl f (f e x)) (inits xs)
  = e : scanl f (f e x) xs

The second-to-third line uses the displayed fold equation as an equality of functions of ys. Hence the efficient left scan is:

scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl f e [] = [e]
scanl f e (x:xs) = e : scanl f (f e x) xs

On a finite input of length

n

, fully demanding the original prefix-fold results performs

0 + 1 + \dots + n = n (n + 1) /2

accumulator updates. The recurrence performs

n

. Thus the update count improves from $Θ (n^{2})$ to $Θ (n)$ , assuming constant-cost updates. Both return

n + 1

results. This does not assert constant space for arbitrary accumulators or imply that lazy accumulators are evaluated strictly.

d

 0  0

Solution

 0  0

Prove the natural-number fold fusion law pointwise. At Zero,

f (foldNat g a Zero) = f a = b = foldNat h b Zero

Assuming the equation at m, the Succ m calculation is:

f (foldNat g a (Succ m))
  = f (g (foldNat g a m))
  = h (f (foldNat g a m))
  = h (foldNat h b m)
  = foldNat h b (Succ m)

The compatibility premise f . g = h . f justifies the middle rewrite. This proves the theorem for finite total constructor values by structural induction.

For the full lazy Haskell interpretation, also handle the bottom value: foldNat g a is strict in its outer Natural constructor, so its value on bottom is bottom; the assumed strict function property of f makes the left side bottom too. The same zero/successor induction now covers finite partial constructor chains. Pure definable functions preserve the limits of these information approximations, extending equality to infinite Succ chains. This explains the strictness premise; finite total induction alone would not use it.^[ref]

5

 0  0

a

 0  0

Solution

 0  0

A divide-and-conquer algorithm handles small base cases directly, divides a larger instance into smaller instances of the same problem, solves them recursively, and combines their answers. The savings come from the number and sizes of recursive calls and the combination cost.

For Karatsuba multiplication, split the

n

-bit inputs as

x = a B + b

y = c B + d

, where

B = 2^{k}

and

k = ⌈ n /2 ⌉

. Compute only three recursive products:

p = a c, q = b d, r = (a - b) (c - d) .

(1)

Then the Karatsuba three-product identity gives

x y = p B^{2} + (p + q - r) B + q .

(2)

The absolute differences have at most

k

bits; multiply their magnitudes and restore the sign of

r

. Additions, subtractions and shifts cost

O (n)

bit operations. With constant-size base cases, the recurrence relation is

T (n) = 3 T (⌈ n /2 ⌉) + O (n)

, giving $O (n^{l o g_{2} 3})$ by the Master theorem. The difference-product version avoids an extra carry bit in the recursive operands.

b

 0  0

Solution

 0  0

Use minimum search in a rotated distinct array, then return the cyclic predecessor of the minimum:

rotatedMaximum(A):
    n = length(A)                 # require n >= 1
    lo = 0
    hi = n - 1
    while lo < hi:
        mid = floor((lo + hi) / 2)
        if A[mid] > A[hi]:
            lo = mid + 1
        else:
            hi = mid
    return A[(lo + n - 1) mod n]

The loop invariant says that the minimum index lies in the inclusive interval. If A[mid] > A[hi], the rotation break lies to the right of mid; otherwise the segment from mid to hi is increasing and its indices after mid cannot be the minimum. Each update at least halves the interval. Distinct entries make the comparison decisive, including a completely unshifted array. The predecessor of the unique minimum is the maximum, and the one-element case returns that element. The running time is $O (lo g n)$ , with

O (1)

auxiliary space.

c

 0  0

Solution

 0  0

For fixed

a \geq 1

b > 1

and

d \geq 0

, a version of the Master theorem states that, with bounded positive base costs,

T (n) = a T (n / b) + Θ (n^{d}), p = lo g_{b} a ⟹ T (n) = ⎩ ⎨ ⎧ Θ (n^{p}), Θ (n^{p} lo g n), Θ (n^{d}), d < p, d = p, d > p .

(1)

Usual floors and ceilings preserve these bounds when a sufficiently large constant-size base case ensures strict size decrease.

$A$ : $T_{A} (n) = 3 T_{A} (⌈ 2 n /3 ⌉) + Θ (1)$ , hence $O (n^{l o g_{3/2} 3})$ , with exponent approximately $2.7095$ . Base cases must include $n \leq 2$ because the ceiling otherwise need not decrease.
$B$ : $T_{B} (n) = 9 T_{B} (⌈ n /3 ⌉) + O (n^{2})$ , hence $O (n^{2} lo g n)$ by comparison with the equality recurrence having $Θ (n^{2})$ overhead. If that overhead is actually quadratic this is also tight; the stated upper bound alone does not establish a matching lower bound.
$C$ : $T_{C} (n) = 3 T_{C} (n - 1) + Θ (1)$ , whose expansion is a geometric series, hence $O (3^{n})$ , in fact $Θ (3^{n})$ for nonzero base costs. The divide-by-a-constant Master theorem does not apply to a decrement by one.

$B$ is asymptotically fastest; $C$ is slowest. Even the quadratic-logarithmic upper bound for

B

is smaller than the tight polynomial order of

A

6

 0  0

a

 0  0

Solution

 0  0

A strongly connected component is a maximal set of vertices that are mutually reachable in a directed graph; a vertex reaches itself by a length-zero path. The condensation graph, also called the SCC graph, contracts each such component to one vertex and retains directed edges between different components. It is a Directed acyclic graph, since a cycle of components would make them mutually reachable and therefore one component.

For an original seven-vertex example, take cycles

a \to b \to c \to a

d \to e \to d

f \to g \to f

, and add

c \to d

e \to f

. The three components are ${a, b, c}$ , ${d, e}$ and ${f, g}$ . Their condensation is the three-vertex directed chain in that order: there is no return edge from a later component to an earlier one.

Figure 1.
Seven vertices with three strongly connected components and their condensation
. An original example. Internal cycles provide mutual reachability; the two forward connecting edges cannot merge distinct components. **Details**.

b

 0  0

Solution

 0  0

Apply the two-pass strongly connected component algorithm:

1. Run depth-first search over all vertices of

G

, recording their finish order.
2. Construct the graph transpose by reversing every edge.
3. Mark every vertex unvisited again. In decreasing first-pass finish order, start a transpose search whenever the next vertex is unvisited. The vertices newly reached by each search form one strongly connected component.

The finish order prevents a second-pass search from entering a different still-unassigned component, while mutual reachability makes it visit the entire current component. With adjacency lists, each traversal and the transposition scan takes

O (∣ V ∣ + ∣ E ∣)

time. Thus the total worst-case time is $Θ (∣ V ∣ + ∣ E ∣)$ , including isolated vertices.

c

 0  0

Solution

 0  0

Because the vertex set is finite, at least one vertex occurs infinitely often, so

Inf (ρ)

is nonempty. Let

u, v

belong to this set. After any chosen visit to

u

, a later visit to

v

exists; the intervening edges give a directed walk from

u

v

. After that visit to

v

, a later visit to

u

also exists, giving a walk in the other direction. Removing repeated portions gives directed paths if desired.

Thus every pair in

Inf (ρ)

is mutually reachable and belongs to the same strongly connected component. This proves the claimed inclusion, which need not be equality: an infinite walk can repeatedly follow one cycle while omitting other vertices in its component. This is the recurrence-set part of the infinite walk criterion in a finite directed graph.

d

 0  0

Solution

 0  0

An infinite trace exists exactly when a directed cycle is reachable from $s$ , by the infinite walk criterion in a finite directed graph. Compute the reachable set with depth-first search, compute its strongly connected components, and return true if any component has at least two vertices or contains a self-loop. A singleton without a self-loop does not qualify.

If the test succeeds, follow a path from

s

to the cycle and traverse the cycle forever. Conversely, an infinite trace in a finite graph repeats a vertex, producing a reachable nonempty closed walk and hence a directed cycle. Reachability, component construction and the self-loop check all scan adjacency lists only a constant number of times. The worst-case time is $O (∣ V ∣ + ∣ E ∣)$ , with

O (∣ V ∣ + ∣ E ∣)

auxiliary space for a straightforward transpose-based implementation.

7

 0  0

a

 0  0

Solution

 0  0

A spanning tree is a connected acyclic subgraph containing every vertex of the original undirected graph. For a graph with

∣ V ∣

vertices it has

∣ V ∣ - 1

edges. A minimum spanning tree minimizes the sum of its edge weights over all spanning trees:

T \in spanning trees S argmin e \in S \sum w (e) .

(1)

Connectedness guarantees existence for a finite graph; equal weights can permit several minimizers.

b

 0  0

Solution

 0  0

Kruskal's algorithm sorts the edges and accepts an edge precisely when it joins two currently different connected components of a graph. A disjoint-set data structure maintains those components:

Kruskal(V, E, w):
    A = empty set
    make one disjoint set for each vertex in V
    for (u,v) in E sorted by nondecreasing w:
        if find(u) != find(v):
            add (u,v) to A
            union(u,v)
            if size(A) == size(V) - 1:
                break
    return A

An accepted edge merges two trees of the current forest. An edge within one component would complete a graph cycle and is skipped. On connected input, after

∣ V ∣ - 1

acceptances the forest is a spanning tree. For a one-vertex graph the empty set is already the answer.

c

 0  0

Solution

 0  0

It is a greedy algorithm because it commits at every step to the cheapest remaining edge that can be added without creating a graph cycle, without revising earlier choices. The minimum spanning tree cut property explains why these locally cheapest admissible choices can be extended to an optimal spanning tree.

d

 0  0

Solution

 0  0

Processing by increasing weight, Kruskal's algorithm accepts

df

of weight one and

c f

of weight two, then rejects

c d

of weight three because its endpoints are already connected. It accepts

a c

e h

f h

, skips

d e

, accepts

b e

, skips

b c

, and accepts

e g

. Seven accepted edges now connect all eight vertices.

The resulting minimum spanning tree is

{df, c f, a c, e h, f h, b e, e g}, w (T) = 1 + 2 + 4 + 5 + 6 + 8 + 10 = 36.

(1)

The remaining heavier edges are unnecessary once the tree is complete. Distinct edge weights also imply that this minimum spanning tree is unique.

Figure 1.
Minimum spanning tree of weight 36 and its component-merging construction
. The solution highlights the seven selected edges. The second panel distinguishes the six distinct first-round choices from the joining edge fh selected in the second round. **Details**.

e

 0  0

Solution

 0  0

The procedure is Borůvka's algorithm. In the first round, visiting singleton components in the order

a, b, c, d, e, f, g, h

, the chosen edges are respectively

a c, b e, c f, df, e h, df, e g, e h .

(1)

The set of new edges is ${a c, b e, c f, df, e h, e g}$ : repeated selections of

df

and

e h

insert no extra copy. The resulting two components are

{a, c, d, f}

and

{b, e, g, h}

. Each chooses

f h

in round two, producing the weight-36 tree from part (d). The within-round order of distinct insertions can therefore be

a c, b e, c f, df, e h, e g

, followed by

f h

in the next round; it need not be the globally sorted Kruskal order.

The required minimum spanning tree cut property says: for every nonempty proper subset

C \subset V

, the unique minimum-weight edge crossing the cut

(C, V ∖ C)

belongs to every minimum spanning tree. Indeed, add this edge to a tree that lacks it. The resulting cycle contains another edge crossing the cut, which is strictly heavier; replacing that edge decreases the total weight.

For the general proof, assume all edge weights are distinct. Fix the components at the beginning of a round, as the given procedure does. Each selected edge is the unique lightest edge across one of their cuts, so belongs to every minimum spanning tree. Inductively, the entire selected set is contained in such a tree and is therefore acyclic. While there is more than one component, connectedness supplies an outgoing edge for each, so at least two components merge. The finite process terminates connected. A connected subgraph of a spanning tree must be that whole tree, proving that the returned set is a minimum spanning tree.

8

 0  0

a

 0  0

Solution

 0  0

Dynamic programming stores answers to overlapping subproblems so they can be reused. Its optimal substructure requirement, the principle of optimality, says that an optimal answer's remaining subproblem solution must itself be optimal once the final decision and state are fixed.

For global sequence alignment without mismatches, use the two prefix lengths as the state. A final column is either a letter of the first string opposite a gap, a gap opposite a letter of the second, or two equal letters. Removing that column leaves one of three smaller prefix problems. If its alignment were suboptimal, replacing it by a better alignment would improve the whole answer. Many different alignments reach the same prefix state, making reuse valuable. Unequal-letter columns and double-gap columns are forbidden, rather than assigned ordinary finite penalties.

b

 0  0

Solution

 0  0

Let

D_{i, j}

be the optimal score for aligning the complete prefixes of lengths

i, j

. The boundary values and recurrence are

D_{0, 0} = 0, D_{i, 0} = - g i, D_{0, j} = - g j,

(1)

D_{i, j} = max {D_{i - 1, j} - g, D_{i, j - 1} - g, D_{i - 1, j - 1} + 1 only if x [i - 1] = y [j - 1]} .

(2)

The last candidate is omitted when the letters differ. Fill rows or columns in increasing index order and return $D_{m, n}$ . The final-column cases in part (a) exhaust all legal alignments and each can be appended to an optimal smaller alignment, proving the recurrence by induction on

i + j

There are

(m + 1) (n + 1)

entries and at most three constant-time candidates per interior entry. Thus the time is $O (mn)$ for positive

m, n

, or

O (mn + m + n + 1)

including empty-input boundary cases, with the same full-table space bound. Computing only the score can reduce auxiliary storage to

O (min (m, n) + 1)

by retaining two rows. This is global sequence alignment without mismatches; admitting a diagonal move on unequal letters would solve a different problem.

c

 0  0

Solution

 0  0

Store one maximizing predecessor together with every table value. For alignment traceback, start at

(m, n)

and follow these pointers:

$(i - 1, j - 1)$ emits x[i-1] opposite y[j-1]; the letters are equal because that diagonal candidate was allowed only on a match.
$(i - 1, j)$ emits x[i-1] opposite a gap.
$(i, j - 1)$ emits a gap opposite y[j-1].

Continue to

(0, 0)

, including boundary moves, then reverse the collected columns. Any deterministic choice among tied predecessors gives an optimal alignment. Each step decreases at least one index, so reconstruction costs $O (m + n)$ additional time and output space. The full score table or predecessor table requires

O (mn)

storage for positive lengths.

d

 0  0

Solution

 0  0

Enumerate all pairs of contiguous substrings, run the global algorithm on each pair, and take the largest score, also allowing the empty alignment of score zero. There are

O (m^{2})

substrings of the first input and

O (n^{2})

of the second. Each call costs at most

O (mn)

for positive lengths, giving the requested upper bound $O (m^{3} n^{3})$ . Substrings are contiguous; enumerating arbitrary subsequences would be a different search.

e

 0  0

Solution

 0  0

For local sequence alignment without mismatches, let

L_{i, j}

maximize the score of alignments of a suffix of each prefix of lengths

i, j

, allowing both suffixes to be empty. Initialize

L_{i, 0} = L_{0, j} = 0

and fill

L_{i, j} = max {0, L_{i - 1, j} - g, L_{i, j - 1} - g, L_{i - 1, j - 1} + 1 only if x [i - 1] = y [j - 1]} .

(1)

Zero starts a new alignment; the remaining candidates append the possible last columns. The same optimal-substructure argument as before proves the recurrence. Because

g \geq 0

, an alignment with a negative-scoring leading portion can be improved by dropping that portion, which is exactly what the zero reset permits.

Return $max_{0 \leq i \leq m, 0 \leq j \leq n} L_{i, j}$ , since an optimal pair of substrings may finish before either full string ends. The time is $O (mn)$ for positive input lengths, with

O (mn)

full-table space or linear rolling-row space for the score alone. If an alignment is wanted, start alignment traceback at a maximum entry and stop at zero. No mismatching diagonal is introduced.

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms (A10097W1)

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion