Source paper: released examination archive, member a10097w1-2.pdf; original cover dated 2016-09-16.
The Haskell type signatures are take :: Int -> [a] -> [a] and drop :: Int -> [a] -> [a]. These definitions also handle nonpositive counts as the Prelude does:
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs

drop n xs | n <= 0 = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xs
The wildcard in the first equation matters under lazy evaluation: take 0 undefined yields [] without inspecting its list argument. The remainder of this question uses nonnegative counts.[ref]
For finite, defined lists, structural induction requires and for every head and tail . This proves for every finite list.
An infinite list cannot be reached by finitely many constructor steps. For structural induction on lazy lists, also check , where is the bottom value, and require an admissible predicate on lazy lists: if increasingly defined finite approximations all satisfy , their limit does too. Together with the empty-list and constructor cases this covers finite, partial and infinite lists. Merely asserting the two finite-list cases is insufficient; “the list is finite” itself satisfies those cases but fails on infinite lists.
Use mathematical induction on , which is finite even when the list is infinite. At , the left side is [] ++ xs = xs. For the successor step, an empty list gives []; for x:xs, the defining equations and list concatenation give
take (n+1) (x:xs) ++ drop (n+1) (x:xs)
= (x : take n xs) ++ drop n xs
= x : (take n xs ++ drop n xs)
= x : xs
The last step applies the induction hypothesis to the tail. A bottom value tail is allowed: for a wholly undefined list and a positive count both sides are undefined. Thus the equality is observationally valid for finite and infinite lists; no evaluation of an infinite length is used.
For finite lists and , the answers are
reverse (xs ++ ys) = reverse ys ++ reverse xs
length (drop n xs) = max 0 (length xs - n)
The maximum is necessary when the count exceeds the list length.
Write u = take n xs, v = drop n xs, and len = length xs. Part (c) gives xs = u ++ v; part (d) gives length v = len-n because . Use the finite-list laws take (length v) (v ++ w) = v, length (reverse v) = length v, and reverse (reverse v) = v. Then equational reasoning gives
reverse (take (len-n) (reverse xs))
= reverse (take (length v) (reverse (u ++ v)))
= reverse (take (length (reverse v)) (reverse v ++ reverse u))
= reverse (reverse v)
= v
= drop n xs
The first and second steps use the decomposition and the length equation; the third uses reversal of a concatenation; the fourth uses the stated take law. This is an algebraic proof using established laws, rather than a new induction proof.
All three Haskell definitions have filter :: (a -> Bool) -> [a] -> [a]. A recursive list filter is
filter p [] = []
filter p (x:xs)
  | p x       = x : filter p xs
  | otherwise = filter p xs
A list comprehension gives filter p xs = [x | x <- xs, p x]. A right fold gives
filter p = foldr (\x ys -> if p x then x:ys else ys) []
Each version retains the input order and needs no equality or Haskell Ord class constraint on the element type.
Use merge sort, then project the second component of each pair. Under the ordinary Haskell Ord class instance for pairs, “ascending” means lexicographic order, requiring both component types to be ordered:
sort :: (Ord a, Ord b) => [(a,b)] -> [b]
sort = map snd . mergeSort

mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort left) (mergeSort right)
  where (left,right) = splitAt (length xs `div` 2) xs

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x <= y    = x : merge xs (y:ys)
  | otherwise = y : merge (x:xs) ys
If the intended convention is to sort only by the first component as a sort key, replace x <= y by fst x <= fst y and specialize the merge routines to pairs. The weaker signature is then sort :: Ord a => [(a,b)] -> [b], and equal keys keep their original order. These conventions differ when first components tie; the question does not explicitly specify that tie rule.
Merging two sorted lists consumes one head per comparison and takes time in their combined length, assuming constant-cost comparisons. Computing the length and splitting also takes time. The balanced recursion therefore satisfies
(1)
Each recursion level has total linear work, and there are levels. Thus merge sort takes worst-case time. The final map snd adds , preserving the bound. Costs of comparing variable-size keys must be included separately.
All three denote iterate :: (a -> a) -> a -> [a], producing . With lazy evaluation, demanding and fully evaluating the first elements costs for f1 and f2, and worst-case for f3, under the unit-cost application assumption.
In f1 the next state is obtained with one new application of g. In f2, the shared binding xs points back to the already generated list; each new element maps g over a shared predecessor once. In f3, the recursive f3 g x is a fresh computation. Producing output position passes through separately constructed map layers, so a strict g causes applications. A non-strict function such as const 0 can avoid work, so the quadratic statement is a worst-case evaluation bound, not a lower bound for every possible g. Merely demanding the outer list spine without its elements is a different cost question.
Map over the optional payload, preserving failure:
mapMaybe :: (a -> b) -> Maybe a -> Maybe b
mapMaybe _ Nothing = Nothing
mapMaybe f (Just x) = Just (f x)
This is the optional-value mapping operation, equivalent to fmap for Maybe. The question's local name is distinct from the library function Data.Maybe.mapMaybe, which filters and maps an entire list. The algebraic data type keeps absence separate from every ordinary payload value.
The most general type signature is foldMaybe :: (a -> b) -> b -> Maybe a -> b. The Nothing branch returns the default of type b; the Just branch applies the supplied function to an a, also producing a b.
Separate the maximal decimal prefix from the unconsumed suffix, rejecting an empty prefix:
import Data.Char (isDigit, digitToInt)

type Parse a = String -> Maybe (a,String)

parseInt :: Parse Int
parseInt input =
  case span isDigit input of
    ([],_)  -> Nothing
    (ds,ys) -> Just (foldl (\n d -> 10*n + digitToInt d) 0 ds, ys)
The left fold uses the positional notation recurrence . This parses unsigned decimal operands as illustrated, leaving the first nondigit and everything after it untouched. As the required result type is Int, correct mathematical values require the parsed integer to fit that bounded type; arbitrary-length exact values would instead need Integer or an explicit integer overflow check.
The parser recognizes exactly one leading operator character:
parseOp :: Parse Char
parseOp (c:cs)
  | c `elem` "+-*/" = Just (c,cs)
parseOp _ = Nothing
An empty input fails, and any later characters remain for the next parser. The last example printed in this part uses the name parseInt; its failure result does not change the requested operator parser.
Compose the three parsing stages using the supplied fold, and accept only when no suffix remains:
eval :: String -> Maybe Int
eval input = foldMaybe first Nothing (parseInt input)
  where
    first (a,rest) = foldMaybe (second a) Nothing (parseOp rest)
    second a (op,rest) = foldMaybe (finish a op) Nothing (parseInt rest)
    finish a op (b,rest)
      | null rest = Just (apply op a b)
      | otherwise = Nothing
    apply '+' a b = a+b
    apply '-' a b = a-b
    apply '*' a b = a*b
    apply '/' a b = a `div` b
    apply _ _ _ = error "unreachable: parseOp rejected this operator"
Every failed intermediate parser is converted to Nothing by foldMaybe. Checking null rest rejects both a second operation and trailing letters. In particular, integer division makes eval "34/4" = Just 8. As permitted by the question, division by zero is outside the specified inputs; the bounded-Int proviso also applies to arithmetic results.
A type synonym is a name for an existing type expression, introduced with type, for example type Name = String. It improves documentation and makes type signatures easier to maintain. It creates no new distinct type: a synonym and its expansion remain interchangeable. An algebraic data type declared with data or newtype has a different role.
Use
type Point = (Double,Double)
type Polygon = [Point]
A valid polygon is a finite list of at least three vertices in boundary order, with the final vertex connected back to the first. The first vertex is not repeated at the end. A simple polygon also has no intersecting nonadjacent edges. Numerical routines below use finite coordinates; NaN and infinite coordinates are outside this representation's intended domain.
The Euclidean distance is
distBetween :: Point -> Point -> Double
distBetween (x,y) (u,v) = sqrt ((x-u)^2 + (y-v)^2)
Thus . The type synonym expands to pairs of floating-point coordinates.
First include the closing edge exactly once:
edges :: Polygon -> [(Point,Point)]
edges [] = []
edges ps = zip ps (tail ps ++ [head ps])

perimeter :: Polygon -> Double
perimeter = total . edges
  where total [] = 0
        total ((p,q):es) = distBetween p q + total es

perimeterFold :: Polygon -> Double
perimeterFold = foldr (\(p,q) s -> distBetween p q + s) 0 . edges
The recursive version and right fold both sum the Euclidean distances between consecutive vertices, including the last-to-first pair. They take linear time. The empty-list convention gives zero, although an empty list is not a valid polygon.
Equal side lengths alone are insufficient: a nonsquare rhombus is not a regular polygon. Use the regular polygon edge rotation criterion: for , successive nonzero edge vectors must be related by the same rotation through either or .
regular :: Polygon -> Bool
regular ps
  | length ps < 3 = False
  | otherwise = norm2 (head es) > 0 && (fits 1 || fits (-1))
  where
    es = [ (u-x,v-y) | ((x,y),(u,v)) <- edges ps ]
    angle = 2*pi / fromIntegral (length ps)
    norm2 (x,y) = x*x+y*y
    close x y = abs (x-y) <= 1e-10 * max 1 (max (abs x) (abs y))
    same (x,y) (u,v) = close x u && close y v
    turn s (x,y) = (cos angle*x - s*sin angle*y,
                    s*sin angle*x + cos angle*y)
    fits s = and (zipWith (\a b -> same (turn s a) b)
                          es (tail es ++ [head es]))
With exact real coordinates and exact equality in same, this is an if-and-only-if test for an ordinary convex regular polygon, in either boundary orientation. The displayed Double implementation tests that condition to the stated tolerance; it cannot promise exact geometric classification near the tolerance boundary. Both orientations are needed, and using the fundamental turn excludes regular star traversals. A repeated zero-length side fails the exact criterion.
Here “centroid” means the vertex centroid, the arithmetic mean of the listed vertices, rather than the uniform-area centroid of the polygon's interior:
centroid :: Polygon -> Point
centroid [] = error "centroid: empty vertex list"
centroid ps = (sx/n,sy/n)
  where
    (sx,sy) = foldr (\(x,y) (u,v) -> (x+u,y+v)) (0,0) ps
    n = fromIntegral (length ps)
The nonempty input restriction prevents division by zero; computing both sums and the length takes linear time.
Apply the same translation to every vertex:
translate :: Point -> Polygon -> Polygon
translate (u,v) = map (\(x,y) -> (x+u,y+v))
Every edge vector is unchanged because the added displacement cancels on subtraction. Hence lengths, angles, orientation and shape are preserved.
Translate the vertex centroid to the origin, rotate, and translate back:
rotatePoly :: Polygon -> Double -> Polygon
rotatePoly ps theta =
  (translate c . map turn . translate (-cx,-cy)) ps
  where
    c@(cx,cy) = centroid ps
    turn (x,y) = (cos theta*x + sin theta*y,
                 -sin theta*x + cos theta*y)
This follows the supplied rotation matrix, so positive rotates clockwise in the usual Cartesian axes. The opposite signs give the conventional counterclockwise matrix. Since the vertex centroid of the centered vertices is zero and a linear map commutes with their average, the final centroid remains c.
A connected component of an undirected graph is a maximal set of vertices such that each pair is joined by a path. Equivalently, components are the equivalence classes of the relation “reachable by a path”. The length-zero path ensures that an isolated vertex is a one-vertex component.
Start a depth-first search from each as-yet unlabelled vertex, propagating a fresh component number:
component = 0
for u in V:
    cc[u] = UNLABELLED
for u in V:
    if cc[u] == UNLABELLED:
        visit(u, component)
        component = component + 1

visit(u, label):
    cc[u] = label
    for v in adjacency[u]:
        if cc[v] == UNLABELLED:
            visit(v, label)
A search follows only edges, so every vertex it labels is reachable from its root. Conversely, if a reachable vertex remained unlabelled, a path to it would contain a first edge from a visited vertex to an unvisited one; scanning that edge would visit the latter, a contradiction. Thus each search labels exactly one connected component, proving both directions of the required equivalence.
With an adjacency list, initialization and the outer loop cost . Each vertex is visited once, and the adjacency scans inspect each edge of a graph twice, once from each endpoint. The total worst-case time is therefore , with labels and recursion-stack space. An adjacency matrix representation instead incurs scanning time.
A disjoint-set data structure maintains a partition of a set into pairwise disjoint sets. Make-Set(v) creates the singleton containing a new vertex. Find-Set(v) returns the disjoint-set representative of its current set. Union(u,v) merges the two sets containing its arguments, preserving the partition; it has no effect if they are already the same set. A disjoint-set forest can implement these operations without explicitly moving every member when sets are joined.
Test Find-Set(u) == Find-Set(v). Initially the sets are singleton connected components of the edgeless graph; processing an edge joins precisely the components it connects. By induction over the processed edges, the final sets are exactly the connected components of .
The displayed procedure calls Find-Set times explicitly, since it tests the two endpoints of every edge. Each successful Union decreases the number of sets by one, from initially to finally, so there are Union calls.
These are calls at the displayed pseudocode level. If a concrete Union(u,v) implementation performs two further internal finds rather than accepting already found roots, its implementation adds find invocations. Counting those separately avoids confusing the procedure's explicit call count with the implementation of a disjoint-set union operation.
Use merge sort: recursively sort the left and right halves of the array, then merge their ordered outputs using two advancing indices. A merge reads or writes each element a constant number of times, so it costs . There are balanced recursion levels with total work per level. Hence the worst-case running time is ; the standard array implementation uses auxiliary storage.
Yes, if a merge takes from its left half when two sort keys compare equal. Within each half the induction hypothesis preserves equal-key order. Across the two halves every left-half occurrence originally preceded every right-half occurrence, and the tie rule preserves that order. Reversing the tie rule would lose stable sorting.
On distinct opaque keys, a comparison sorting algorithm must distinguish all input orders. Its binary decision tree has at least leaves, because one fixed permutation of the input positions cannot correctly sort two distinct strict orders. A tree of height has at most leaves. Therefore some input needs
(1)
The bound is worst-case and specific to algorithms obtaining order information through binary comparisons; it does not apply to every possible representation of keys.
Use counting sort with 26 counters, indexed by the character code minus the code for A. Scan the input to obtain each character's count, then emit that many copies in alphabetic order. Counting costs ; visiting 26 counters and writing outputs costs .
The comparison lower bound does not apply because the algorithm uses a fixed-size known alphabet and direct key indexing. It does not have to distinguish distinct-key orders by binary comparisons; for , distinctness is not even possible in this alphabet.
For bare characters, equal occurrences are indistinguishable. The count-and-reconstruct implementation in (d) nevertheless does not preserve the identities of equal-key records, and so cannot provide stable sorting of associated payloads.
A stable refinement computes cumulative counts , the number of input keys at most , then scans the original records right to left. For a record with key , decrement and place the complete record at output index . Equal-key records are placed from the end of their allocated range in reverse scanning order, preserving their original relative order. This costs time and auxiliary storage.
Precompute the 26 cumulative counts using prefix sums. Then
(1)
and the answer is zero if . Counting and prefix summation take preprocessing time and constant storage for this fixed alphabet. Each query uses two indexed reads and one subtraction, hence time. The guard for prevents a negative answer for an empty interval.
Dynamic programming solves overlapping subproblems once and stores their values for reuse. The principle of optimality says that the remaining decisions within an optimal solution must solve the corresponding residual subproblem optimally; otherwise replacing them by a better residual solution would improve the original one. Here removing one chosen stamp leaves an optimal way to form the remaining postage.
Let be the minimum number of stamps for total . Since denomination 1 is available, every nonnegative total is reachable. The dynamic programming recurrence is
(1)
Fill the table in increasing order of :
F[0] = 0
for x = 1,...,m:
    F[x] = infinity
    for i = 1,...,n:
        if d[i] <= x:
            F[x] = min(F[x], 1 + F[x-d[i]])
return F[m]
Every representation of has a last stamp , so its remaining count is at least . Conversely, appending to an optimal residual representation attains each candidate. Thus the recurrence is exact by the principle of optimality. Worst-case time is , with storage. This is pseudo-polynomial time in the numerical target, rather than polynomial time in its binary encoding length.
Whenever an update improves , store choice[x] = i. Starting at x = m, repeatedly increment count[choice[x]] and subtract that denomination from x, stopping at zero. The invariant is that the selected stamps plus an optimal representation of the residual total attain the original optimum; every step reduces by one. Reconstruction uses steps and output counters, preserving the total time bound.
The greedy algorithm repeatedly takes the largest denomination no greater than the remaining postage. For denominations and target , it returns , using three stamps. The optimum is , using two. Thus local preference for the largest stamp does not generally solve the coin change problem optimally.
Use greedy coin change for powers of an integer, with integer . In any optimal solution, there can be no or more stamps of denomination for : replacing of them by one stamp preserves value and reduces the stamp count by .
Consequently each lower-denomination count lies in , and their total value is at most
(1)
The number of largest stamps must therefore be , leaving a residual below . Apply the same argument successively to lower powers. This forces exactly the greedy quotients, proving optimality. For , only unit stamps are available and the conclusion is immediate. Integer is essential to the carry argument and follows from the stated integer denominations whenever denomination is present.
A spanning tree is a connected acyclic subgraph containing every vertex. A minimum spanning tree minimizes the sum of edge weights over all spanning trees. In a three-vertex triangle with every edge weight 1, deleting any of the three edges gives a different spanning tree of total weight 2. Hence there are three minimum spanning trees; minimum total weight need not mean a unique tree.
True. Every spanning tree contains precisely the vertex set by definition. Thus every minimum spanning tree has nodes, independently of the weights or which minimum tree is chosen.
True. Every finite tree on vertices has exactly edges. One proof removes a leaf and its incident edge, preserving a tree on one fewer vertex, and applies induction from the one-vertex tree. Therefore all minimum spanning trees have the same edge count.
False. Take a triangle with and . Its unique minimum spanning tree uses and , with total weight 4. The shortest path from to in the original graph is the direct edge of weight 3; the tree's only path has weight 4. A minimum spanning tree optimizes total tree weight, not every pairwise path length.
Prim's algorithm grows a tree from any root . For each vertex outside the current tree, its priority queue key is the cheapest single edge connecting it to the tree, not the total length of a root-to-vertex path:
for v in V:
    key[v] = infinity
    parent[v] = NONE
key[r] = 0
Q = indexed_min_priority_queue(V, key)
while Q is not empty:
    u = Q.extract_min()
    for (v,weight) in adjacency[u]:
        if Q.contains(v) and weight < key[v]:
            parent[v] = u
            key[v] = weight
            Q.decrease_key(v, weight)
return {(parent[v],v) : v != r}
The indexed priority queue supports membership and locating a vertex's heap entry. After the first extraction, the chosen parent edge is a least-weight edge crossing the cut between the current tree and its complement. The minimum spanning tree cut property makes that edge safe: exchanging it for a crossing edge of a suitable minimum tree preserves minimality. Repeating this establishes a minimum tree. Connectivity ensures every nonroot vertex eventually has a parent; edge weights may be negative.
An indexed binary heap builds the initial queue in time; extract_min and decrease_key each cost , while a position table supports membership in . There are extractions and at most edge inspections, with at most one successful decrease per inspection. Thus the bound is , or for a connected graph with at least two vertices. The singleton case is constant time. An unindexed heap cannot provide decrease-key by vertex without an additional position structure.

Ancestors (9)

  1. 2016
  2. Past exam of the year 1 of the computer science course of the University of Oxford
  3. Year 1 of the computer science course of the University of Oxford
  4. Computer science course of the University of Oxford
  5. Undergraduate course of the University of Oxford
  6. Course of the University of Oxford
  7. University of Oxford
  8. List of universities
  9. Home

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