The three answers, in source order, are:
- . In the Master theorem, , , and grows polynomially faster than . The regularity condition holds because . For powers of three, expansion even gives .
- , and hence . The telescoping sum is .
- . Set and . Then , with constant base cost for . The Master theorem with , applies because is polynomially smaller than . Finally .
The change of variable in the third case handles the additive shift in the recursive argument exactly; it is not an unjustified deletion of the
+1. These Big theta notation conclusions use the usual admissible input sizes, or bounded integer rounding of subproblem sizes.Repeatedly remove vertices whose current degree is less than . Implement the deletions with an adjacency list, a queue and a degree counter for each active vertex:The requested subgraph is understood to be nonempty; otherwise an empty output would make the degree requirement vacuous or undefined. For , any nonempty input graph already qualifies.
active[v] = True for every v
count[v] = degree(v)
queue all v with count[v] < k
while the queue is nonempty:
remove v from the queue
if not active[v]: continue
active[v] = False
for each neighbour u of v:
if active[u]:
count[u] -= 1
if count[u] == k-1: queue u
return the subgraph induced by the active vertices,
or report failure if there is no active vertexThe correctness invariant is that every subgraph with minimum degree at least has all its vertices still active. Initially this is immediate. When is deleted, its degree in the whole active induced subgraph is less than . Any candidate subgraph on active vertices has at most that many incident edges at , so cannot contain it. Thus the invariant survives every deletion.
At termination, every active vertex has current degree at least , since every counter initially below the threshold or subsequently crossing it was queued. A nonempty surviving induced subgraph is therefore a valid answer. If none survives, the invariant rules out every possible answer, including ones omitting additional edges. The result is the k-core, with the k-core peeling invariant proving that deletion order cannot destroy a valid solution.
Each vertex is enqueued at most once when initially deficient or first crossing the threshold. Each adjacency list is scanned once when its vertex is deleted. The running time is , and storage is including the input graph.
TakeIts longest strictly increasing subsequences have length two. A subsequence starting with can continue with or with , but cannot use both in increasing order; one starting at has only after it.
The specified greedy algorithm may choose the longest increasing subsequence . The remaining sequence is , which needs two singleton increasing subsequences. The algorithm then uses three subsequences in total.
However, and partition the original sequence into two increasing subsequences. One is impossible because the original sequence is not increasing. Hence two is optimal and the greedy choice is suboptimal. This establishes the counterexample to removing a longest increasing subsequence without relying on a tie-breaking rule: the problem asks for a longest choice that can fail.
Write each undirected edge with its smaller endpoint first. Kruskal's algorithm orders candidates first by weight and then lexicographically:Thus the requested addition order isand the minimum spanning tree has total weight . Five accepted edges connect all six vertices, so the remaining weight-four edges need not be scanned.
The minimum spanning tree cut property says: if a cut of a graph respects an edge set contained in some minimum spanning tree, a minimum-weight edge across that cut is safe to add to , meaning that some minimum spanning tree contains together with that edge. Respecting means no edge of crosses the cut. In particular, any lightest cut edge belongs to some minimum spanning tree; a uniquely lightest cut edge belongs to every minimum spanning tree.
For the exchange argument, take a minimum spanning tree containing . If it lacks the chosen edge , add to create its fundamental cycle. The remaining route between 's endpoints crosses the cut at some edge , with . Since the cut respects , . Replacing by preserves a spanning tree, retains , and cannot increase weight. Hence it is also minimum. Strict inequality would contradict minimality, which gives the unique-lightest assertion.
For an illustration, take a triangle with weights , , . Across the cut , is the unique lightest edge and must be in every minimum spanning tree. The minimum tree is , of weight . With tied light edges, the existence assertion need not mean that every minimum spanning tree contains the particular tied edge chosen.
Let , , and let be the minimum number of words chosen from , in their given order, whose concatenation equals the length- prefix of a list of . Use for impossibility. The boundary values areFor ,Here denotes indices . The first case omits . In the second, the last selected word is , so removing it leaves a solution using only earlier words for the shorter prefix. These are exhaustive alternatives. Conversely either alternative constructs a valid solution, proving the dynamic programming recurrence. Even an empty word causes no cycle because both alternatives use row .
Fill rows in increasing and store the chosen alternative for every finite entry. If , report no solution. Otherwise trace back from : a skip moves to ; a take records index and moves to . Reverse the recorded indices to obtain the required subsequence. Ties may choose either valid predecessor.
There are states. A substring comparison costs , so under the given bounds and the running time is , with storage including reconstruction choices. Two rows give working storage if only the optimum count is needed. For the source example, the optimum is three words, indices , whose concatenation is
010111. This is ordered word concatenation dynamic programming.Sort the open intervals by increasing left endpoint. Scan them in that order, maintaining the largest right endpoint among previously seen intervals. For the next interval , report an intersection if ; otherwise set and continue. Equality is allowed: and do not meet because the intervals are open. For zero or one interval, return that they are mutually non-intersecting.
If , a previous interval with right endpoint has left endpoint at most and has positive length. Together with , this guarantees an interior common point. Conversely, if , every earlier interval ends at or before , so none intersects the new one. This loop invariant proves correctness. A comparison sort costs time and the scan costs .
For the lower bound, transform an input of integers for the element distinctness problem intoEqual integers produce identical, intersecting intervals. Unequal integers differ by at least one, so their intervals are disjoint. The answer therefore decides whether all the integers are distinct. Moreover, comparing any two constructed endpoints can be simulated by comparing their original integers and, only on equality, their fixed offsets or . Thus the transformation preserves the comparison model, rather than gaining extra information from arithmetic on arbitrary endpoints. The supplied distinctness lower bound gives comparisons, matching the upper bound. This is the comparison lower bound for interval disjointness.
Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 5 c Solution Created 2026-10-25 Updated 2026-11-05
First run breadth-first search, ignoring weights, to obtain the minimum number of edges from the source to each reachable vertex. Then compute weighted distances only along edges that advance one breadth-first layer:Unreachable vertices keep distance . For an undirected graph, scan both orientations of each edge.
d[source] = 0; all other d[v] = infinity
for u in nondecreasing BFS-layer order:
for each outgoing edge (u,v):
if h[v] == h[u]+1:
if d[u]+w(u,v) < d[v]:
d[v] = d[u]+w(u,v)
predecessor[v] = uTo justify discarding other routes, a shortest path can be taken simple because every weight is positive. A simple path of edges has weight inEvery path with at least edges weighs at least . Consequently every minimum-weight path must also have the minimum possible number of edges: this is minimum-hop dominance for nearly unit weights.
A minimum-hop path to uses exactly edges. Every prefix of such a path must itself have minimum hop count, since replacing a longer prefix by a shorter one would shorten the whole route. Hence it advances from layer to layer at every step. The retained edges form a directed acyclic graph, ordered by . The displayed dynamic programming recurrence therefore finds the cheapest of all minimum-hop paths, which by the preceding bound is a true shortest path.
With an adjacency list, both the breadth-first search and the layer-ordered relaxations take time and total storage, where . The queue order from breadth-first search already supplies the layer order; no sorting or priority queue is needed. This improves the usual binary-heap Dijkstra bound and is linear in the input size.
Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 5 b Solution Created 2026-10-25 Updated 2026-11-05
Take the directed graph with source and weighted edgesIt is a directed acyclic graph, so has no negative-weight graph cycle. The true shortest path to is , of weight .
The standard label-setting shortest-path algorithm version of the Dijkstra algorithm extracts , then at distance , then at distance , and only then at distance . Thus it finalises instead of . Even if an implementation subsequently changes the stored label of the already settled vertex , it does not reprocess its outgoing edge to , so the error at remains. Allowing repeated reprocessing would instead be a label-correcting shortest-path algorithm, not the usual Dijkstra guarantee.
A tree fold can compute insertion while retaining the unchanged children by carrying a pair. The following fold-derived implementation preserves the lazy evaluation behaviour of part (f):The invariant of the folded pair is
insertViaFold :: Ord a => a -> Tree a -> Tree a
insertViaFold q t = snd (foldTree node base t)
where
base = (Empty, Tree Empty q Empty)
node ~(l,li) x ~(r,ri) = (original,updated)
where
original = Tree l x r
updated = case compare q x of
LT -> Tree li x r
EQ -> original
GT -> Tree l x ri(original subtree, subtree with q inserted). The empty case establishes it. At a node, the first components reconstruct the original tree, and the second components supply whichever child insertion is needed. The irrefutable pair patterns ~(l,li) and ~(r,ri) avoid demanding an unused child's fold. Induction on finite approximations therefore proves equivalence even for partial trees, and only the selected search route needs insertion work.There is a distinction if “written as a fold” is required to mean a direct same-result-type expression Here
insert q = foldTree node base, with no richer result and final projection. On finite fully defined binary search trees, such an expression is possible by undoing insertion of a new extreme key in the child that should remain unchanged. For completeness, a literal direct fold on that finite, fully defined domain is:eraseFresh :: Ord a => a -> Tree a -> Tree a
eraseFresh _ Empty = Empty
eraseFresh q (Tree l x r) = case compare q x of
LT -> Tree (eraseFresh q l) x r
EQ -> Empty
GT -> Tree l x (eraseFresh q r)
insertDirectFold :: Ord a => a -> Tree a -> Tree a
insertDirectFold q = foldTree node (Tree Empty q Empty)
where
node left x right = case compare q x of
LT -> Tree left x (eraseFresh q right)
EQ -> Tree (eraseFresh q left) x (eraseFresh q right)
GT -> Tree (eraseFresh q left) x righteraseFresh is used only to undo a newly inserted extreme key, which is a leaf; it is not a general deletion operation. The binary search tree bound at each root guarantees exactly that precondition on every child being restored.On all partial Haskell trees, however, a direct expression with result type
Tree a cannot implement part (f).For that obstruction, fix Both can be completed to valid right subtrees of a root labelled
q = 0, and consider the two right subtreesr1 = Tree Empty undefined Empty
r2 = Tree Empty undefined (Tree Empty 3 Empty)1. Yet insert 0 r1 and insert 0 r2 are both bottom, because insertion must compare 0 with their undefined root label. A direct fold equal to insertion would therefore receive the same folded left value, root 1, and bottom folded right value on both larger trees Tree Empty 1 r1 and Tree Empty 1 r2. It must return the same result. Part (f) instead preserves r1 or r2, which are distinguishable by inspecting their right-child constructors without inspecting the undefined labels. This proves the direct-fold obstruction. The pair-valued implementation avoids losing that information and states precisely which sense of fold implementation is being used.Insert down the unique search route, leaving equal elements unchanged:The binary search tree ordering determines the only child in which a missing query can belong. The recursive call preserves that child's ordering bounds, and the other child is shared. Thus the output represents the original set with
insert :: Ord a => a -> Tree a -> Tree a
insert q Empty = Tree Empty q Empty
insert q t@(Tree l x r) = case compare q x of
LT -> Tree (insert q l) x r
EQ -> t
GT -> Tree l x (insert q r)q added, with duplicates suppressed. Its time complexity and newly allocated route length are ; it makes no balancing guarantee.Fold into a membership predicate:At an empty tree the predicate is always false. At a nonempty binary search tree, an unequal query can occur only in the indicated child, while equality finds the root. This proves correctness inductively. Under lazy evaluation, the unused folded child is not demanded; lookup follows one root-to-leaf route and takes comparisons in a tree of height . Defining the predicate by a fold does not require visiting both subtrees for each query.
find :: Ord a => Tree a -> a -> Bool
find = foldTree node (const False)
where
node left x right q = case compare q x of
LT -> left q
EQ -> True
GT -> right qUse the remaining ascending list itself as the seed:The empty seed produces
buildUnfold :: [a] -> Tree a
buildUnfold = unfoldTree split
where
split [] = Nothing
split xs =
let (ls,x:rs) = splitAt (length xs `div` 2) xs
in Just (ls,x,rs)Empty. Every nonempty seed produces exactly the midpoint and two child seeds used by build. Thus the defining equations agree, and structural induction on the finite input proves buildUnfold xs = build xs. The balance and ordering arguments carry over unchanged.Choose the middle element as the root:The input is a finite, strictly ascending list, as required for distinct elements of a set. The two child lengths differ by at most one. Applying the same argument recursively gives a balanced binary tree of logarithmic height. All values on each side retain their original order, proving the binary search tree property. With linked lists, the repeated splitting gives time; it does not repeatedly insert values into a skewed tree.
build :: [a] -> Tree a
build [] = Empty
build xs = Tree (build ls) x (build rs)
where
(ls,x:rs) = splitAt (length xs `div` 2) xsThe direct tree fold for an inorder traversal isBy structural induction, the child lists are ascending; the binary search tree property places every left value below the root and every right value above it. The displayed list concatenation therefore gives an ascending list containing every stored value exactly once.
flattenFold :: Tree a -> [a]
flattenFold = foldTree (\ls x rs -> ls ++ (x:rs)) []For a version with linear time complexity on every tree shape, use an accumulator:This also has a higher-order tree fold expression using difference lists:Its folded value is a function that prepends the inorder traversal to a supplied tail. The accumulator invariant is
flatten :: Tree a -> [a]
flatten t = onto t []
where
onto Empty zs = zs
onto (Tree l x r) zs = onto l (x : onto r zs)flattenLinear :: Tree a -> [a]
flattenLinear t =
foldTree (\l x r -> l . (x:) . r) id t []onto t zs = flattenFold t ++ zs. Each node contributes one constructor, giving time to consume the output. By contrast, the direct list-valued fold can take on a left-skewed tree because ++ repeatedly copies left traversals. There are unlisted articles, also show them or only show them.
