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

Solutions to the readable material from the 12 September 2017 resit: 24 printed subparts in Questions 4–8. Source: released examination archive, member 2016/L/a10097w1.pdf. The cover establishes the 2017 date despite the archive directory name.

TODO: Printed pages 2–3, containing Questions 1–3, are absent or unrenderable in the held source. Their contents and subpart labels cannot be recovered from the different June examination.

Table of contents

1

Solution

TODO: Question 1 is on the unavailable printed pages 2–3. No statement, subpart structure or solution is inferred from a different paper.

2

Solution

TODO: Question 2 is on the unavailable printed pages 2–3. No statement, subpart structure or solution is inferred from a different paper.

3

Solution

TODO: Question 3 is on the unavailable printed pages 2–3. No statement, subpart structure or solution is inferred from a different paper.

4

a

Solution

The most general polymorphic type is

unfold :: (s -> Bool) -> (s -> a) -> (s -> s) -> s -> [a]

The stopping predicate consumes a state, the output function turns that state into one list element, and the transition function supplies another state of the same type. The state type and output type need not coincide. This is a list unfold with separate stopping, output and transition arguments.

b

Solution

The standard Haskell definition and principal type are

iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)

Under lazy evaluation, this produces successive states

x, f (x), f (f (x)), \dots

as demanded. An infinite spine does not require all elements to be evaluated at once; productivity still depends on the demanded computations terminating.

c

Solution

The required function composition is

unfold p f g = map f . takeWhile (not . p) . iterate g

iterate g supplies the successive states, takeWhile (not . p) retains precisely those before the first stopping state, and map f produces their outputs. If the initial state satisfies the stopping predicate, both sides return the empty list. Otherwise both emit the same head and repeat from g x; the same argument applies to every demanded finite prefix of an infinite result.

d

Solution

Using the specified list unfold, the definitions are

map f     = unfold null (f . head) tail
iterate f = unfold (const False) id f

For map, the current state is the remaining input list. null prevents head and tail from being evaluated on an empty list. For iterate, the stop predicate is always false and the output is the current state itself. Its transition is f, so the original seed is emitted before the first application of f.

e

Solution

Store two consecutive Fibonacci numbers as the state:

fibs :: [Integer]
fibs = unfold (const False) fst step (0,1)
  where
    step (a,b) = (b,a+b)

The invariant is that the state is

(F_{n}, F_{n + 1})

, with

F_{0} = 0, F_{1} = 1

. Emitting its first component and updating the pair therefore produces $0, 1, 1, 2, 3, 5, 8, \dots$ . Integer avoids fixed-width overflow; the bit cost of adding increasingly large integers is separate from the number of unfold steps.

f

Solution

Arrange that each state already begins with the next passing element, or is empty:

filter p = unfold null head next . seek
  where
    seek = dropWhile (not . p)
    next = seek . tail

The initial seek skips the rejected prefix. After an element is emitted, next removes it and skips the following rejected run. Thus null guards both partial list operations and the filtering a list by unfolding invariant is preserved.

For a finite input of length

n

and constant-cost predicate evaluation, each input element is tested once and each list cell is passed a bounded number of times: the total work is $O (n)$ , as for the usual recursive list filter. This version may have different constant overhead. Recomputing dropWhile independently in the stopping, output and transition expressions could repeat scans; keeping the already-filtered suffix as state avoids that. On an infinite rejected tail, finding another output diverges, just as the standard lazy filter does.

5

a

Solution

Initialize

d [s] = 0

and every other tentative distance to infinity. The Bellman-Ford algorithm repeatedly relaxes every directed edge:

for v in V: d[v] = infinity; parent[v] = none
d[s] = 0
repeat |V|-1 times:
    changed = false
    for each edge (u,v) of weight w:
        if d[u] != infinity and d[u] + w < d[v]:
            d[v] = d[u] + w
            parent[v] = u
            changed = true
    if not changed: break
for each edge (u,v) of weight w:
    if d[u] != infinity and d[u] + w < d[v]:
        report a reachable negative-weight cycle

An unreachable vertex retains infinity. A reachable negative-weight cycle prevents finite shortest-walk distances for vertices reachable from that cycle, so the detection case must not be reported as an ordinary finite answer. With edge-list scans the worst-case work is $O (∣ V ∣∣ E ∣ + ∣ V ∣)$ , conventionally stated as

O (∣ V ∣∣ E ∣)

, and the auxiliary storage is

O (∣ V ∣)

beyond the graph.

b

Solution

Every finite distance label is the weight of a discovered directed walk, so it can never underestimate a finite shortest-path distance. After

k

complete passes, each label is at most the cost of every source-to-vertex path using at most

k

edges. To prove that assertion, consider such a path's last edge

u \to v

: after the previous pass,

u

already has a label no greater than the prefix cost, and the current pass relaxes that last edge. In-place improvements can only make the label smaller, preserving the assertion.

When no negative-weight cycle is reachable, any repeated-vertex portion of an optimal walk can be removed without increasing its cost. Some shortest path therefore has at most

∣ V ∣ - 1

edges. The two bounds meet after that many passes, proving correctness. If a complete pass makes no change, all edge relaxation inequalities already hold and further passes cannot improve anything. A further strict relaxation after

∣ V ∣ - 1

passes implies a reachable negative cycle by the same simple-path bound.

c

Solution

Bellman–Ford permits negative edge weights, and can detect a reachable negative-weight cycle. The usual settled-label Dijkstra's algorithm requires nonnegative weights for its correctness argument. Negative edges are not themselves a problem for Bellman–Ford when no relevant negative cycle exists.

d

Solution

Use minimum-hop shortest paths by minimizing the lexicographic order pair

(d, h)

: total weight first, number of edges second. Extend a pair across an edge of weight

w

by adding

(w, 1)

, and compare the full pair in both the priority queue and relaxation:

for v in V: key[v] = (infinity,infinity)
key[s] = (0,0)
Q = indexed min-priority-queue containing all vertices, keyed by key
while Q is not empty:
    u = extract-min(Q)
    if key[u].distance == infinity: break
    for each edge (u,v) of weight w with v still in Q:
        candidate = (key[u].distance + w, key[u].hops + 1)
        if candidate <lex key[v]:
            key[v] = candidate
            decrease-key(Q,v,candidate)
for v in V: best[v] = key[v].hops

All weights are positive, so extending a path strictly increases its first component. The usual Dijkstra's algorithm settled-label proof therefore applies to these ordered pairs: no path through a not-yet-settled vertex can later improve an extracted minimum. Among equal minimum weights, the secondary component selects the fewest edges. Merely breaking extraction ties by vertex name would not implement this objective.

With a binary heap and adjacency lists, the bound is $O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)$ , with

O (∣ V ∣)

extra storage. Unreachable vertices have best = infinity. In the paper's example, the resulting pairs in order

s, a, b, c, d, e, f

are

(0, 0), (2, 1), (2, 1), (4, 1), (5, 2), (5, 2), (6, 3)

, so the requested edge counts are $0, 1, 1, 1, 2, 2, 3$ .

6

a

Solution

Dynamic programming defines subproblem optima and combines their stored answers through a recurrence. It is useful when optimal substructure and overlapping subproblems allow repeated work to be shared. Several alternative choices can be compared before an optimum is selected.

A greedy algorithm instead commits to a locally selected choice and does not later reconsider it. To be correct, its choice needs a justification such as an exchange argument or a safe-cut property, beyond merely having optimal substructure. Neither method is automatically applicable to every optimization problem. Prim's algorithm illustrates a justified greedy choice; the maximum-segment recurrence below illustrates dynamic programming.

b

Solution

For a connected, weighted, undirected graph, grow a tree from any root

r

. For every vertex outside the tree, store the cheapest edge currently connecting it to the tree, not its source-path distance:

for v in V: key[v] = infinity; parent[v] = none
key[r] = 0
Q = indexed min-priority-queue containing all vertices
while Q is not empty:
    u = extract-min(Q)
    if parent[u] != none: output edge (parent[u],u)
    for each edge {u,v} of weight w with v still in Q:
        if w < key[v]:
            key[v] = w
            parent[v] = u
            decrease-key(Q,v,w)

The maintained key chooses the minimum-weight edge crossing the cut between the tree and remaining vertices. The minimum spanning tree cut property makes that edge safe; induction therefore preserves the existence of a minimum spanning tree containing all selected edges. This proves why Prim's algorithm is greedy and correct. With adjacency lists and a binary heap its time is

O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)

. For a disconnected graph, starting another component when the minimum key is infinity produces a minimum spanning forest instead of claiming that a spanning tree exists.

c

Solution

Let

e_{i}

be the best sum of a segment ending at position

i

, allowing the empty segment with sum zero. The maximum subarray problem recurrence is

e_{0} = 0, e_{i} = max (0, e_{i - 1} + a_{i}), B_{i} = max (B_{i - 1}, e_{i}), B_{0} = 0.

An optimal nonempty segment ending at

i

extends the best suffix ending at

i - 1

, or starts fresh; a negative suffix cannot help. Keep its start index and record endpoints whenever a new overall best is found:

suffix = 0; best = 0
start = 0; bestLeft = 0; bestRight = 0
for i = 0,...,n-1:
    suffix = suffix + A[i]
    if suffix < 0:
        suffix = 0; start = i+1
    if suffix > best:
        best = suffix
        bestLeft = start; bestRight = i+1
return A[bestLeft:bestRight]

The half-open endpoint interval is empty initially, so empty input and all-negative input correctly return an empty segment. The invariant identifies the best nonnegative suffix and the best segment in the scanned prefix, proving correctness. This is Kadane's algorithm, using $O (n)$ time and $O (1)$ auxiliary space, excluding the returned slice. The displayed example yields sum $55$ , from the segment

10, - 5, 40, 10

.

7

a

Solution

Maintain white, gray and black colors for undiscovered, active and completed vertices. A single traversal clock records DFS discovery and finishing times:

for v in V: color[v] = white; parent[v] = none
time = 0
visit(u):
    time = time+1; d[u] = time; color[u] = gray
    for v in adjacency[u]:
        if color[v] == white:
            parent[v] = u
            visit(v)
    color[u] = black; time = time+1; f[u] = time
for u in V:
    if color[u] == white: visit(u)

The outer loop makes a depth-first search forest even when the directed graph is disconnected. Each vertex is entered once and each directed adjacency entry is inspected once. Thus an adjacency list representation gives $O (∣ V ∣ + ∣ E ∣)$ time and

O (∣ V ∣)

auxiliary storage, including the worst-case recursive stack. Sorting neighbors to impose a particular visit order would be additional work.

b

Solution

Relative to the resulting DFS edge classification, a tree edge in depth-first search discovers a white vertex and becomes its parent edge. A forward edge in depth-first search goes to a proper descendant but is not that descendant's discovery edge. A back edge in depth-first search goes to an active ancestor, with a self-loop also counted as a back edge when such edges are allowed. A cross edge in depth-first search joins vertices with no ancestor-descendant relationship in the forest, such as different completed branches or different trees.

The definitions refer to directed edges; an undirected graph is normally classified only with tree and back edges, accounting for the reverse copy of a parent edge separately.

c

i

Solution

False. Use vertices

x, u, v

, edges

x \to u

,

u \to x

,

x \to v

, and start depth-first search at

x

, scanning

u

before

v

. The times are

d (x) = 1, d (u) = 2, f (u) = 3, d (v) = 4, f (v) = 5, f (x) = 6.

There is a directed path

u \to x \to v

and

d (u) < d (v)

, but

u

and

v

are separate children of

x

. Thus

v

is not a descendant of

u

. The path leaves

u

through an already gray ancestor; its later branch need not be explored inside

u

's recursive call. This is consistent with the DFS parenthesis property.

Figure 1.
DFS counterexamples distinguish reachability from tree ancestry
. Left: the path from u through its ancestor x reaches a later sibling v, after u has finished. Right: root order a,u,c makes three singleton DFS trees, though u has an incoming and an outgoing edge. Details.

ii

Solution

False. The same ordered traversal gives a path

u \to x \to v

, but

d (v) = 4 > 3 = f (u) .

A path from

u

can pass through an already discovered ancestor, whose remaining edges are scanned only after

u

finishes. A reachability statement alone therefore does not impose the claimed finishing-time bound.

iii

Solution

True for a directed cycle. Suppose there were no back edges. On examining an edge

u \to v

, its target would either be white, in which case its recursive call finishes before

u

; or black, in which case it has already finished. A gray target would be an active ancestor and hence give a back edge, contrary to the supposition. Therefore every edge would satisfy

f (v) < f (u)

.

Applying those strict inequalities around a directed cycle would imply

f (u) < f (u)

, a contradiction. Thus some back edge in depth-first search must exist in the search's edge classification. Such an edge is classified relative to the DFS forest; it is not one of the forest's tree edges.

iv

Solution

False. Take edges

u \to a

and

c \to u

, and let the outer DFS loop try vertices in order

a, u, c

. The first call finishes

a

immediately. The next discovers

u

, whose only outgoing edge reaches already black

a

, so its tree contains only

u

. Finally

c

sees already black

u

.

u

has both an incoming edge from

c

and an outgoing edge to

a

, yet is the sole vertex of its DFS tree. Nonzero incoming and outgoing degrees do not require either edge to become a tree edge in depth-first search.

8

a

Solution

Build a max-heap, then repeatedly swap its root with the last element of the active prefix, shrink that prefix and restore heap order by heapify down. A zero-based implementation is

for i = floor(n/2)-1,...,0:
    siftDown(A,i,n)
for end = n-1,...,1:
    swap A[0],A[end]
    siftDown(A,0,end)

siftDown(A,i,end) repeatedly exchanges entry i with its larger child while the child lies below end and has a larger key. The suffix beyond end is already sorted and never touched again. For the specified input, key stages of heapsort are

Stage	Active max heap	Sorted suffix
Bottom-up heap construction	$[5, 4, 3, 1, 2]$	$[]$
Extract 5, repair	$[4, 2, 3, 1]$	$[5]$
Extract 4, repair	$[3, 2, 1]$	$[4, 5]$
Extract 3, repair	$[2, 1]$	$[3, 4, 5]$
Extract 2	$[1]$	$[2, 3, 4, 5]$

The final array is $[1, 2, 3, 4, 5]$ . Bottom-up construction takes

O (n)

time because there are progressively fewer nodes at each greater subtree height; the extractions give worst-case

O (n lo g n)

time and constant auxiliary storage for iterative sifting.

b

Solution

A deterministic comparison sort on

n

distinct keys must distinguish

n!

possible initial orders. Its binary comparison decision tree therefore has at least

n!

leaves: a leaf fixes one output ordering and cannot be correct for two different strict orders of the original records.

A binary tree of height

h

has at most

2^{h}

leaves, hence

h \geq ⌈ lo g_{2} (n!)⌉ = Ω (n lo g n) .

This is the comparison sorting lower bound on the worst-case number of comparisons. Distinct keys have only two possible comparison outcomes, even if an implementation's comparator also supports equality. Algorithms exploiting numeric key values, such as counting sort, fall outside this model.

c

Solution

The printed split uses

n

while naming the current length

m = j - i

. For the intended stooge sort, read that split as

k = ⌊ m /3 ⌋

at every recursive call. Keeping one fixed original

n

instead is not the standard algorithm and does not generally sort correctly.

The three recursive calls then each have length

m - ⌊ m /3 ⌋ = ⌈ 2 m /3 ⌉

, and all other work is constant. Thus

T (m) = 3 T (⌈ 2 m /3 ⌉) + Θ (1) (m > 2), T (m) = Θ (1) (m \leq 2) .

A version of the master theorem sufficient here states: if

T (n) = a T (⌈ n / b ⌉) + f (n)

a \geq 1, b > 1

, fixed-size base cases and

f (n) = O (n^{l o g_{b} a - ϵ})

for some

ϵ > 0

, then

T (n) = Θ (n^{l o g_{b} a})

, provided the recursive sizes shrink above the base threshold. Apply it with

a = 3, b = 3/2, f = Θ (1)

to obtain

T (n) = Θ (n^{l o g_{3/2} 3}), lo g_{3/2} 3 \approx 2.7095.

The rounded size is important for correctness; it does not change this asymptotic exponent.

d

Solution

Prefer the alternatives for large unrestricted arrays. Merge sort and heapsort have

O (n lo g n)

worst-case time, while insertion sort has

O (n^{2})

worst-case time and can be much faster on nearly sorted data. The intended stooge sort has worst-case

Θ (n^{2.7095 \dots})

, so even insertion sort has the better worst-case exponent.

The first two give the stronger general asymptotic guarantee. Choices between them can depend on storage and stable sorting requirements; these considerations do not rescue Stooge sort's much larger work count.

e

Solution

No: Stooge sort is not stable. Give equal keys distinct record identities and start with

[2_{a}, 2_{b}, 1] .

The initial endpoint swap gives

[1, 2_{b}, 2_{a}]

. The later two-element calls either see increasing keys or equal keys, so they make no swap. The two records with key 2 have reversed their original order, contradicting stable sorting. The example uses length three, where the intended current-length split is unambiguous.

 Ancestors (9)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version