Functional programming, design and analysis of algorithms (resit) (A10097W1)

a

Solution

The empty-list case uses

f (a) = b

. At a cons, assuming the equality for the tail, the calculation is

f (foldr g a (x : x s)) = f (g x (foldr g a x s)) = h x (f (foldr g a x s)) = h x (foldr h b x s) .

The middle equality is the supplied compatibility condition, instantiated with the folded tail; the last expression is the right fold on the whole list. Structural induction therefore proves fusion for finite total spines.

The strictness condition accounts for a bottom-valued input spine: the inner list fold returns bottom, and

f (⊥) = ⊥

makes the two sides agree. The same induction covers finite partial lists. For pure definable continuous functions, an infinite list is the limit of its finite partial approximations, so equality extends to it. These are the three distinct obligations in the right-fold fusion law; strictness is not needed if the domain is restricted to finite terminating spines.

b

Solution

Yes. Define the combining function as follows:

takeP :: (a -> Bool) -> [a] -> [a]
takeP p = foldr step []
  where
    step x rest = if p x then x : rest else []

For the fusion derivation use the identity reconstruction foldr (:) [], take

f = takeWhile p

, and choose the displayed step as

h

. The function

f

is strict in the input list,

f ([]) = []

, and its cons equation is exactly

f (x : x s) = h x (f (x s))

. Fusion gives the implementation. On a false test, step does not demand the folded tail, so the implementation can terminate after a finite list prefix even when the remaining list is infinite or undefined. An undefined predicate result at a tested element makes both definitions undefined.

c

Solution

In general, no direct list fold with result type [a] can implement dropWhile p. Choose total values

u, v

for which

p (u) = True

and

p (v) = False

. The results on [] and [u] are both []. A hypothetical implementation foldr h z would therefore receive identical folded-tail values when extending either input by the same head

v

. Yet the required outputs are [v] and [v,u], respectively. This contradicts the fold factorisation criterion: the combining function cannot distinguish information already discarded by its tail summary.

The claim concerns a direct same-result-type list fold. A list fold returning extra information, followed by a projection, is possible: a pair can retain both the original tail and the dropped list suffix. Also, special predicates can have direct list folds: a constantly false predicate gives the identity; a constantly true predicate can use foldr (\_ r -> r) [], which correctly diverges when it must traverse an infinite spine. Those special cases do not supply an implementation for an arbitrary predicate.

d

Solution

The necessary definedness condition is local: every predicate application actually reached before the first false result must produce a Boolean value. No condition is needed on predicate applications after that first false result, because the list suffix is then returned without further testing. If a reached test is bottom at a known cons cell, the reconstructed list is bottom at that position, while the original list still exposes a cons there; equality fails.

To prove sufficiency on finite lists, induct on the spine. The empty case gives [] ++ [] = []. At a true test the left list prefix contributes the head, and the induction hypothesis reconstructs the tail. At a false test the list prefix is empty and the list suffix is the whole current list. For an infinite true-tested list prefix, every finite output list prefix is copied correctly; the infinite list prefix hides the possibly divergent list suffix computation. A partial spine ending in bottom is reconstructed up to exactly the same bottom. Thus finiteness is sufficient for an elementary induction proof but is not itself necessary for the identity.

For the uniform list fold calculation in part (f), use the convenient stronger assumption that the input is a finite total list and the predicate terminates on every element of that list. This makes the reconstruction identity available on every list suffix, not only on the list suffixes visited by the original list prefix scan. A total predicate on the element type ensures this uniformly over all finite total inputs.

e

Solution

For the finite total inputs just specified, a recursive implementation is

spanP :: (a -> Bool) -> [a] -> ([a], [a])
spanP p [] = ([], [])
spanP p whole@(x:xs)
  | p x       = let (ys,zs) = spanP p xs in (x:ys,zs)
  | otherwise = ([],whole)

At a true test, the head belongs to the list prefix and splitting continues on the tail; at a false test, the complete remaining list is the list suffix. Induction proves that the first projection is the longest accepted list prefix and the second projection is the remaining list suffix.

There is a small partial-value distinction behind the paper's displayed pair identity. The conventional recursive span is strict in an entirely undefined list, whereas the literal expression (takeWhile p undefined, dropWhile p undefined) exposes an outer pair with two undefined components. The equality as a pair therefore needs the stated defined-input convention, or an interpretation that compares the two projections. This does not affect the finite total answers here.^[ref]

f

Solution

Yes, under the finite total assumption in part (d). The pair result retains enough information to reconstruct the tail; the ~ pattern keeps its two components lazy:

spanFold :: (a -> Bool) -> [a] -> ([a], [a])
spanFold p = foldr step ([], [])
  where
    step x ~(ys,zs)
      | p x       = (x:ys,zs)
      | otherwise = ([],x:(ys ++ zs))

Take

f = spanP p

g = (:)

and

a = []

. The base image is

([], [])

. If

p (x)

is true, the recursive equation gives the first branch. If it is false, part (d), applied to the tail, gives

ys + + zs = x s

, so the second branch becomes

([], x : x s)

. These are precisely the fusion compatibility equations. Finite structural induction establishes the desired equality; it does not require extending the restricted-domain hypothesis to undefined predicate applications.

The qualification matters. If

p (v)

is false but

p (u)

is undefined, ordinary spanP p [v,u] can return the untouched list suffix immediately, whereas the reconstruction through spanFold p [u] cannot recover that list suffix. The weaker condition needed only for the single reconstruction identity in (d) is therefore insufficient for this particular list fold on all list suffixes. The stronger totality condition stated there supplies exactly the missing premise.

2

a

Solution

A three-way quicksort can use a common partition helper so that the tree factorisation below makes the same key comparisons. The compare operation is assumed to be a terminating lawful total ordering on the supplied keys.

partition3 :: Ord a => a -> [a] -> ([a],[a],[a])
partition3 pivot = foldr step ([],[],[])
  where
    step x rest =
      let (lo,eq,hi) = rest
      in case compare x pivot of
           LT -> (x:lo,eq,hi)
           EQ -> (lo,x:eq,hi)
           GT -> (lo,eq,x:hi)

sort :: Ord a => [a] -> [a]
sort [] = []
sort (pivot:xs) =
  let (lo,eq,hi) = partition3 pivot xs
  in sort lo ++ (pivot:eq) ++ sort hi

Every non-pivot entry appears in exactly one partition, and the equal bucket contains the original pivot exactly once. The recursive sublists have length at most one less than the current finite input, so recursion terminates. Induction gives sorted recursive results with the original multiplicities; placing the equal bucket between them gives a sorted permutation of the input. There is no recursive call on the equal bucket, which avoids needless descent on repeated keys.

b

Solution

The ordering operations used to decide the partitions require an Ord a constraint. A function with parametric polymorphism and type [a] -> [a] cannot inspect arbitrary element values to decide which one is smaller; for example, functions themselves need not admit the comparison operations required by this sorting algorithm. A Haskell Ord class instance supplies the comparison method, with its ordering laws a separate semantic assumption.^[ref]

c

Solution

Store the equal bucket at each internal node:

data Tree a = Empty | Node (Tree a) [a] (Tree a)

toTree :: Ord a => [a] -> Tree a
toTree [] = Empty
toTree (pivot:xs) =
  let (lo,eq,hi) = partition3 pivot xs
  in Node (toTree lo) (pivot:eq) (toTree hi)

fromTree :: Tree a -> [a]
fromTree Empty = []
fromTree (Node left equal right) =
  fromTree left ++ equal ++ fromTree right

The representation invariant for a tree produced by toTree is that its bucket is nonempty and contains equal keys, every left-subtree key is smaller, and every right-subtree key is larger. Its multiplicities are preserved. Substituting the two equations for toTree into fromTree gives exactly the two defining equations for sort; induction proves sort = fromTree . toTree on finite inputs.

Both versions call the same partition helper on the same pivot and sublists. The flattening stage makes no key comparisons. Thus fully producing the answer makes the same comparison decisions as the direct algorithm; no additional comparison against stored tree keys is introduced.

d

Solution

toTree needs Ord a; fromTree does not. Construction compares each key against a pivot. Flattening merely traverses and concatenates the buckets, so its more general type is Tree a -> [a]. A manually constructed tree need not satisfy the search-tree invariant; fromTree still flattens it, although its output need not be sorted.

e

Solution

A tree fold replaces each constructor by its interpretation:

foldTree :: (b -> [a] -> b -> b) -> b -> Tree a -> b
foldTree combine zero Empty = zero
foldTree combine zero (Node left equal right) =
  combine (foldTree combine zero left)
          equal
          (foldTree combine zero right)

fromTreeFold :: Tree a -> [a]
fromTreeFold = foldTree (\left equal right -> left ++ equal ++ right) []

Induction on the finite tree shows equality with fromTree: the empty tree produces the empty output, and the combining function concatenates the two correctly flattened children around the node's bucket. The result type

b

is independent of the key type; other choices can compute a size or another summary using the same structural recursion.

f

Solution

An unfold expands a seed into either no node or a bucket and two new seeds:

unfoldTree :: (s -> Maybe (s,[a],s)) -> s -> Tree a
unfoldTree split seed =
  case split seed of
    Nothing -> Empty
    Just (left,equal,right) ->
      Node (unfoldTree split left) equal (unfoldTree split right)

toTreeUnfold :: Ord a => [a] -> Tree a
toTreeUnfold = unfoldTree split
  where
    split [] = Nothing
    split (pivot:xs) =
      let (lo,eq,hi) = partition3 pivot xs
      in Just (lo,pivot:eq,hi)

The seed is the remaining list. Expanding a nonempty seed partitions it exactly as toTree does, and both child seeds are shorter. Induction establishes toTreeUnfold = toTree and algorithm termination on finite inputs. The unfold separates the local decomposition rule from the recursive construction of the tree.

3

a

Solution

The empty family has one choice, the empty selection:

cp :: [[a]] -> [[a]]
cp = foldr extend [[]]
  where
    extend choices suffixes = [x:ys | x <- choices, ys <- suffixes]

A selection from the whole family consists uniquely of a choice from its first member and a selection from the remaining family. This bijection proves the combining equation and completeness by induction. If a member family is empty, there are no selections. The base is [[]], not []: otherwise every Cartesian product would incorrectly be empty.

b

Solution

For a nonnegative order, first enumerate every possible row and then every possible ordered selection of rows:

squares :: Int -> [[[Int]]]
squares n
  | n < 0     = error "negative order"
  | otherwise = cp (replicate n (cp (replicate n [1..n])))

Every one of the

n^{2}

positions chooses one of

n

symbols independently. Consequently the enumeration contains $n^{n^{2}}$ candidate squares for

n \geq 1

, each exactly once. The conventional order-zero extension produces one empty square. This is generation only; repeated symbols have not yet been rejected.

c

Solution

The following predicate also checks the square's shape; sort is the three-way sorting function from Question 2:

valid :: [[Int]] -> Bool
valid rows =
  let n = length rows
      symbols = [1..n]
      goodRows = all (\r -> sort r == symbols) rows
      goodColumns = all (\j -> sort [r !! j | r <- rows] == symbols)
                        [0..n-1]
  in goodRows && goodColumns

latin :: Int -> [[[Int]]]
latin = filter valid . squares

The row tests guarantee that each row has length

n

and contains each allowed symbol once. Because && tests this condition first, the later column indexing is safe for a finite total input. The column tests establish the remaining Latin-square condition. Filtering therefore retains precisely the valid squares; it does not remove any different ordering of rows, columns or symbols as an alleged symmetry duplicate.

d

Solution

The generation count, before any validity test, is $n^{n^{2}}$ . It is

19683

at order three,

4294967296

at order four, and approximately

2.98 \times 1 0^{17}

at order five. Even an illustrative rate of one million complete candidates per second would require about 72 minutes at order four and about 9,444 years at order five, before accounting for the actual validity-checking cost. Thus order four is already expensive and order five is plainly impractical for this strategy; the exact threshold depends on the implementation and hardware, not just the mathematical count.

Figure 1.
Candidate growth before filtering in two Latin-square generation strategies
. Original exact candidate counts, plotted on a base-ten logarithmic vertical axis. These are mathematical counts, not measured running times; pruning can avoid many invalid partial extensions as well. **Details**.

e

Solution

Choose each row from the permutations of the symbols:

squaresRows :: Int -> [[[Int]]]
squaresRows n
  | n < 0     = error "negative order"
  | otherwise = cp (replicate n (perms [1..n]))

latinRows :: Int -> [[[Int]]]
latinRows = filter valid . squaresRows

Every Latin square remains a candidate, because each of its rows is one of those permutations. Conversely every candidate has valid rows, so only its columns still need checking. There are $(n!)^{n}$ candidates instead of

n^{n^{2}}

: at order four,

331776

rather than more than four billion. The improvement is substantial but does not make exhaustive generation practical at arbitrary orders. One can replace valid by a column-only test here, since row validity is guaranteed by construction.

f

Solution

Generate a row while respecting the forbidden symbols in each column. Selection returns an element together with the still-available elements:

select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- select xs]

row :: [Int] -> [[Int]] -> [[Int]]
row [] [] = [[]]
row remaining (used:otherColumns) =
  [x:rest | (x,available) <- select remaining,
            x `notElem` used,
            rest <- row available otherColumns]
row _ _ = []

latinPruned :: Int -> [[[Int]]]
latinPruned n
  | n < 0     = error "negative order"
  | otherwise = build n (replicate n [])
  where
    build 0 usedColumns = [[]]
    build remainingRows usedColumns =
      [r:rest | r <- row [1..n] usedColumns,
                rest <- build (remainingRows-1)
                              (zipWith (:) r usedColumns)]

The invariant of row is that remaining contains exactly the unused symbols of this row, while each member of the column list records symbols used by earlier rows. Selecting removes a symbol, so it cannot repeat in the current row; the membership test prevents a column repetition. A complete row uses every symbol once. Updating the column histories preserves the invariant for the next recursive call.

Every complete generated square is therefore valid without a final filter. Conversely, take any valid target square: its next row passes every selection and column test, so induction keeps a branch constructing that target. Distinct choices from the initially distinct symbols cannot generate the same square twice. Dead-end partial squares may still be explored; the method promises to avoid constructing complete invalid squares, not to foresee every future dead end. Independent enumeration gives 1, 2, 12 and 576 squares at orders one through four.

4

a

Solution

A function returning an optional value supplies the representation:

newtype List a = List (Int -> Maybe a)

For a finite represented list, require a length

m \geq 0

such that every index

0 \leq i < m

returns Just its element and every other index returns Nothing. Thus there are no holes: absence at a nonnegative index implies absence at every later index. The type alone does not enforce this invariant, or algorithm termination of a query. An infinite represented sequence may instead have a present value at every nonnegative index; operations requiring its length will not terminate.

The implementations below return Nothing at negative indices. Finite lengths, requested counts and intermediate indices are assumed to fit Int; explicit guards on index shifts also prevent arithmetic wraparound from exposing an invalid element.

b

Solution

The empty representation is nowhere present; prepending shifts all old positions by one:

nil' :: List a
nil' = List (\_ -> Nothing)

cons' :: a -> List a -> List a
cons' x (List f) = List query
  where
    query i
      | i < 0     = Nothing
      | i == 0    = Just x
      | otherwise = f (i-1)

For a represented length

m

, cons' represents length

m + 1

, provided that length is representable. Index zero is the new head and each later valid index asks for the preceding old position. The no-holes invariant is preserved. No conventional list is built by either constructor.

c

Solution

The embedding is a right fold interpreting each source constructor by its new counterpart:

list' :: [a] -> List a
list' = foldr cons' nil'

Induction on the finite source list proves that querying index

i

returns its

i

th element exactly when

i

lies in range. The empty case is nil'; the cons case shifts every tail index as established in part (b). This is the only part of Question 4 whose implementation uses the conventional list type.

d

Solution

Inspect index zero for emptiness and the head; removing the head shifts the query in the other direction:

null' :: List a -> Bool
null' (List f) = case f 0 of
                  Nothing -> True
                  Just _  -> False

head' :: List a -> a
head' (List f) = case f 0 of
                  Nothing -> error "head of empty representation"
                  Just x  -> x

tail' :: List a -> List a
tail' input@(List f)
  | null' input = error "tail of empty representation"
  | otherwise   = List query
  where
    query i
      | i < 0 || i == maxBound = Nothing
      | otherwise             = f (i+1)

The no-holes invariant makes the zero-index test sufficient for emptiness. Both head' and tail' have the precondition that the representation is nonempty and signal an error when it is violated. On a nonempty representation, tail' removes exactly one position. The overflow guard is consistent with finite lengths at most maxBound.

e

Solution

Preserve absence and transform only a present value:

map' :: (a -> b) -> List a -> List b
map' g (List f) = List (\i -> case f i of
                              Nothing -> Nothing
                              Just x  -> Just (g x))

Every query keeps its presence status, so the represented length and the no-holes invariant are unchanged. The transformed element is computed only when demanded.

f

Solution

Clamp a nonpositive count to zero. Taking restricts the domain of present indices; dropping translates that domain:

take' :: Int -> List a -> List a
take' count (List f) = List query
  where
    k = max 0 count
    query i
      | i < 0 || i >= k = Nothing
      | otherwise      = f i

drop' :: Int -> List a -> List a
drop' count (List f) = List query
  where
    k = max 0 count
    query i
      | i < 0 || i > maxBound - k = Nothing
      | otherwise                = f (i+k)

length' :: List a -> Int
length' (List f) = countFrom 0
  where
    countFrom i = case f i of
                    Nothing -> i
                    Just _  -> countFrom (i+1)

For finite length

m

, the first two operations give lengths

min (k, m)

and

max (m - k, 0)

, respectively. The length loop reaches the first absent index, namely

m

, so it terminates for a total finite representation. It does not terminate on an infinite represented sequence. There is no assumption that an arbitrary stored query function takes constant time.

g

Solution

Merge by comparing the present heads and consuming just the chosen one. The implementation uses only the functional representation:

merge' :: Ord a => List a -> List a -> List a
merge' left right
  | null' left  = right
  | null' right = left
  | head' left <= head' right =
      cons' (head' left) (merge' (tail' left) right)
  | otherwise =
      cons' (head' right) (merge' left (tail' right))

mergeSort' :: Ord a => List a -> List a
mergeSort' input =
  let n = length' input
      middle = n `div` 2
  in if n <= 1 then input
     else merge' (mergeSort' (take' middle input))
                 (mergeSort' (drop' middle input))

The two recursive inputs are the disjoint initial and final portions of the represented sequence; they preserve every occurrence and have smaller lengths when

n \geq 2

. In merge', the smaller current head can precede every remaining value in both sorted inputs. Selecting the left head on equality preserves stability. Each merge step reduces the total number of remaining elements, and induction proves a sorted permutation of the original sequence.

This establishes algorithm termination and correctness on total finite representations, not an unconditional

O (n lo g n)

implementation bound. Nested index functions can make queries costly, and repeatedly finding lengths or heads may revisit them. The familiar merge-sort bound assumes suitable constant-time access or consumption primitives; the source's function-only representation supplies no such cost guarantee.

5

a

Solution

There are three unnumbered cases inside this leaf.

For the nine-child recurrence, a recursion tree has

9^{j}

subproblems of size about

n / 3^{j}

. There are

Θ (n^{2})

constant-size leaves, and the total unit work over earlier levels is a geometric sum of the same order. Hence $T (n) = Θ (n^{2})$ . This is also the first case of the master theorem, since

lo g_{3} 9 = 2

and the additive work is constant.

For the decrementing recurrence, summing from the supplied base at three gives

T (n) = 1 + \sum_{j = 4}^{n} j = \frac{n ( n + 1 )}{2} - 5 (n \geq 3),

so $T (n) = Θ (n^{2})$ here as well. Values at the smaller base indices remain one as specified.

For the recurrence that squares its recursive result, set

S (n) = lo g_{2} T (n)

. Then

S (n) = 1 + 2 S (⌊ n /2 ⌋)

above the base range. Let

d (n) = min {j \geq 0 : ⌊ n / 2^{j} ⌋ \leq 3} = max (0, ⌊ lo g_{2} n ⌋ - 1) (n \geq 1) .

After

d

expansions,

S (n) = 1 + 2 + \dots + 2^{d - 1} = 2^{d} - 1

, giving the exact answer

T (n) = 2^{2^{d (n)} - 1} .

(3)

For powers of two

n \geq 4

this is

2^{n /2 - 1}

. For arbitrary positive integer

n

, the exact values form plateaux:

T (4) = \dots = T (7) = 2

, while

T (8) = \dots = T (15) = 8

. In general $T (n) = 2^{Θ (n)}$ . It is not

Θ (2^{n /2})

uniformly over integer

n

: near the top of a plateau the exponent is closer to

n /4

. Keeping the integer halving is essential; the ordinary linear master theorem does not apply to squaring

T

b

Solution

Sequential accumulation writes merged outputs of lengths

2 n, 3 n, \dots, kn

. Its total work is

Θ (n \sum_{j = 2}^{k} j) = Θ (n k^{2}) (k \geq 2) .

The growing list prefix is repeatedly copied, even though its internal order is already known.

Instead, divide the family of arrays into two nearly equal halves, recursively merge each half, and merge the two resulting sorted arrays. A balanced merge tree has

⌈ lo g_{2} k ⌉

levels; at each level at most

kn

entries are read or written in merges. Thus the bound is $Θ (kn lo g k)$ for $k \geq 2$ , including the output work. Equivalently the recurrence in the number of arrays is

M (k) = M (⌊ k /2 ⌋) + M (⌈ k /2 ⌉) + Θ (kn)

. The one-array case simply returns it, or costs

Θ (n)

if a fresh output array is required.

c

Solution

A strict majority element in the whole array must be a strict majority element in at least one half: otherwise summing the two non-majority element frequency bounds would give at most half of all entries. This observation supplies at most two candidates, but they must still be verified in the whole subarray.

majority(A, left, right):
    if left == right: return NoMajority
    if right - left == 1: return Candidate(A[left])
    middle = floor((left + right)/2)
    first = majority(A, left, middle)
    second = majority(A, middle, right)
    for candidate in the two returned tagged results:
        if candidate is Candidate(x):
            count = 0
            for i from left to right-1:
                if A[i] == x: count = count + 1
            if 2*count > right-left: return Candidate(x)
    return NoMajority

NoMajority is a separate result tag, not a possible input element. The two-candidate loop does not require ordering, hashing or conversion of arbitrary elements to a set. It may count the same candidate twice without changing correctness or the bound.

Induction proves the recursive candidates correct. If the whole subarray has a majority element, the observation ensures it reaches the verification step; if a candidate passes the strict frequency test, it really is a majority element. The worst-case recurrence has two balanced recursive calls and linear combination work, so the running time is $Θ (n lo g n)$ , with

O (lo g n)

auxiliary recursion depth when the array is passed by index ranges. A different cancellation-based method can achieve linear time, but is not needed for this divide-and-conquer construction.

6

a

Solution

Treat array entries as indexed occurrences, so equal numerical values may be selected independently. Put

S = \sum_{j = 1}^{n} a_{j} \leq nk

. Reject

s < 0

s > S

. Define

D_{i} (t)

to mean that some subset of the first

i

indices sums to

t

. The base is

D_{0} (0) = True

and all other base entries are false. Considering whether index

i

is selected gives

D_{i} (t) = D_{i - 1} (t) \lor (t \geq a_{i} \land D_{i - 1} (t - a_{i})) .

Only

0 \leq t \leq s

is needed, because all entries are positive. A one-dimensional implementation is

subsetSum(A, s):
    S = sum of A
    if s < 0 or s > S: return false
    D[0..s] = false
    D[0] = true
    for each indexed entry a in A:
        for t from s down to a:
            D[t] = D[t] or D[t-a]
    return D[s]

Descending updates make both right-hand-side values belong to the previous list prefix: when updating

t

, the smaller location

t - a

has not yet been updated for this entry. This prevents using the same occurrence repeatedly. Induction on the list prefix proves the recurrence and the returned answer.

The time is

O (n (s + 1)) \subseteq O (n^{2} k)

for nonempty input with

k \geq 1

, and space is

O (s + 1) \subseteq O (nk)

. More generally one may fill through

S

and answer every target from the same table. For a two-way equal partition, reject odd

S

; otherwise ask for target

S /2

. A selected subset with that sum leaves its complement with the same sum. These are bounds polynomial in the numerical bound

k

; without that bound the method is pseudopolynomial in a binary-encoded unrestricted target.^[ref]

b

Solution

Let

S

again be the total. Reject unless

S

is divisible by three, and put

h = S /3

. Define

D_{i} (x, y)

to mean that the first

i

occurrences can be assigned to three groups so that the first two groups have sums

x

and

y

. Their third sum is already determined by the processed list prefix sum minus

x + y

, so it need not be stored as another coordinate.

Initialize

D_{0} (0, 0)

true and all other states false. For each reachable state, assign the next occurrence to exactly one group:

threeEqualParts(A):
    S = sum of A
    if S mod 3 != 0: return false
    h = S/3
    D[0..h,0..h] = false
    D[0,0] = true
    for each indexed entry a in A:
        Next[0..h,0..h] = false
        for x from 0 to h:
            for y from 0 to h:
                if D[x,y]:
                    Next[x,y] = true
                    if x+a <= h: Next[x+a,y] = true
                    if y+a <= h: Next[x,y+a] = true
        D = Next
    return D[h,h]

The three transitions put the occurrence in the third, first or second group, respectively. Using a fresh layer prevents reusing it. Conversely, deleting the last occurrence from any valid list prefix assignment leaves exactly one predecessor state, so induction proves completeness as well as soundness. At the final state

(h, h)

, the third sum is

S - 2 h = h

, giving precisely the required disjoint partition.

There are

(h + 1)^{2}

states per layer and a constant number of transitions per state. Thus the time is $O (n (h + 1)^{2}) \subseteq O (n^{3} k^{2})$ , and rolling layers use $O ((h + 1)^{2}) \subseteq O (n^{2} k^{2})$ space for nonempty inputs. The source mentions an additional integer

s

in this part, but it does not occur in the stated equal-partition condition; the required target is determined by

S

. Empty groups are allowed by the stated subset formulation.

7

a

Solution

Use a global clock starting at zero, incrementing once on discovery and once on finish. Scan starting vertices and each adjacency list in increasing numerical order. The first search descends through

1, 2, 5, 7, 4

, returns from

4

, and then visits

6

from

7

. After that search finishes, the unvisited vertex

3

starts a second tree.

v π (v) d (v) f (v) 1 - 112 21211 3 - 1314 47565231067787549

A dash denotes a root with no predecessor. $2 \to 6$ is a forward edge: vertex

6

is a proper descendant of

2

, but its predecessor is

7

. Its interval satisfies

d (2) < d (6) < f (6) < f (2)

. $4 \to 1$ is a back edge, because

1

is still an active ancestor when it is examined. The other non-tree edge

4 \to 5

is also a back edge, while

3 \to 6

reaches an already finished vertex in a different search tree.^[ref]

b

Solution

Use the two-pass strongly connected component algorithm: first run depth-first search on the original directed graph, then search its graph transpose in decreasing order of the first pass's finishing times. The first-pass order from part (a) is

3, 1, 2, 5, 7, 6, 4.

Reversing the edges gives outgoing adjacency lists

1 : (4), 2 : (1), 3 : (), 4 : (7), 5 : (2, 4), 6 : (2, 3, 7), 7 : (5) .

The second pass first visits only

3

. Its next new root is

1

, whose search visits

1, 4, 7, 5, 2

; later entries already marked by this search are skipped. The next new root is

6

, whose graph transpose neighbours have already been assigned. Therefore the components are

{3}, {1, 2, 4, 5, 7}, {6} .

(3)

Within the middle component the directed cycle

1 \to 2 \to 5 \to 7 \to 4 \to 1

demonstrates mutual reachability. The source edge structure does not provide return paths from

6

or to

3

. More generally, decreasing finish order chooses a remaining component whose graph transpose search cannot escape to another still-unassigned component, so each second-pass tree is exactly one component. This explains the partition rather than merely listing it. The algorithm takes

O (∣ V ∣ + ∣ E ∣)

with adjacency lists.^[ref]

c

Solution

Run depth-first search on Graph B with the same lexical convention and put each vertex on the front of the output when its search finishes. The finish order is

4, 6, 7, 5, 2, 1, 3,

so the returned topological order is

3, 1, 2, 5, 7, 6, 4.

For example, both edges from

1

point to later entries, the edges from

5

point to

4

and

7

later in the order, and

3

precedes

6

. The construction is valid because in a Directed acyclic graph every edge

u \to v

has

f (u) > f (v)

: a newly found descendant finishes before its caller, and an already finished neighbour also has a smaller finish time; an active ancestor would instead witness a directed cycle. Thus reversing the finish order puts every prerequisite before its successor. The time is

O (∣ V ∣ + ∣ E ∣)

d

Solution

Take reachability to include a path of length zero. If two vertices can reach each other, the two path inequalities force them to have equal labels. Conversely, equal labels force mutual reachability: a missing path in either direction would require a strict inequality. Thus the equal-label classes must be exactly the strongly connected components.

Two different components must also be comparable by reachability. If neither could reach the other, applying the no-path condition in both directions would require both

ℓ (a) > ℓ (b)

and

ℓ (b) > ℓ (a)

. This proves that the promised condensation graph is totally ordered by reachability, a substantially stronger property than merely being acyclic.

Compute the components, form the condensation graph, and find a topological order

C_{1}, \dots, C_{r}

. Assign

ℓ (v) = i for v \in C_{i} .

A path goes within one component or forward in this order, so its labels are nondecreasing. Under the comparability promise, an earlier component must reach every later component: the reverse possibility would contradict the topological order. Therefore no path from

a

b

means that

a

lies in a strictly later component, giving exactly the required strict inequality. This proves both parts of the specification.

For a new example, use vertices

u, v, w, x, y

, edges

u \to v, v \to u, v \to w, w \to x, x \to y, y \to x

. Its components are

{u, v}, {w}, {x, y}

in that order, and assigning labels

1, 1, 2, 3, 3

works. Every earlier component reaches each later one through the displayed chain.

Figure 1.
An original example whose strongly connected components are ordered by reachability
. This five-vertex example is separate from the examination's two source graphs. Internal cycles receive equal labels; the component chain forces strictly increasing labels between components. **Details**.

Component computation, scanning original edges to build the condensation graph, topological sorting, and expanding component labels all take $O (∣ V ∣ + ∣ E ∣)$ . Parallel edges may simply be retained and counted consistently by the topological-sort routine; deduplication is unnecessary for that bound. An empty graph returns the empty mapping.

8

a

Solution

For denominations $1, 3, 4$ and target $6$ , greedy selects

4 + 1 + 1

, using three coins. The representation

3 + 3

uses two coins and is optimal because there is no denomination six. Hence choosing the largest affordable coin is not generally optimal.

b

Solution

Write

c_{j} = 2^{j} + 1

for

0 \leq j \leq k

, with a separate unit denomination. Choose, among all minimum-coin representations of the target, one whose vector of counts is lexicographically largest when larger denominations come first. Such a choice exists because a fixed positive target has only finitely many representations.

There cannot be two unit coins: replacing them by one

c_{0} = 2

decreases the count. For

j < k

, two copies of

c_{j}

can be exchanged using

2 c_{j} = c_{j + 1} + 1.

This keeps the coin count unchanged but increases the first differing larger-denomination count, contradicting the chosen lexicographic maximum. Thus there exists an optimal representation using at most one of each denomination below the largest. The largest denomination may repeat.

It remains to show why that normalization implies greedy optimality; uniqueness alone is not enough for an arbitrary coin system. Fix a denomination

c_{j}

. Let

L

be the total value of all coins smaller than

c_{j}

in the chosen optimal representation, and let

r

be their number. These smaller coins are distinct. If

I \subseteq {0, \dots, j - 1}

records the selected non-unit denominations, then

L = \sum_{i \in I} 2^{i} + r, \sum_{i \in I} 2^{i} \leq 2^{j} - 1.

L \geq c_{j}

, replace all

r

smaller coins by one

c_{j}

and

L - c_{j}

unit coins. The new number of coins is

1 + L - c_{j} = L - 2^{j} \leq r - 1,

(3)

contradicting optimality. Therefore the total value below every denomination $c_{j}$ is strictly less than $c_{j}$ .

At the largest denomination, this forces its count to be

⌊ n / c_{k} ⌋

: its residual value is nonnegative and smaller than

c_{k}

. Remove those coins. The same smaller-denomination property then forces the next quotient, and so on down to the unit coin. These are exactly greedy's choices, proving greedy is optimal for every positive target. The argument also covers

k = 0

, where the denominations are two and one. Independent comparison with coin-change dynamic programming confirmed the formula for all

0 \leq k \leq 8

and targets from one to 2,000; that finite check supplements the proof.

c

Solution

Serve customers in nondecreasing service time, with ties broken arbitrarily. The objective in the source includes each customer's own service time, so these are completion times, not only delays before service begins. If the order is

σ

, then

T = \sum_{j = 1}^{n} (n - j + 1) t_{σ (j)} .