Functional programming, design and analysis of algorithms (4208)

a

Solution

The map function changes each element of a list while preserving its order and length. List concatenation removes one level of nesting. Currying changes a function on a pair into a function taking its two arguments separately; uncurrying reverses this conversion:

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

concat :: [[a]] -> [a]
concat []       = []
concat (xs:xss) = xs ++ concat xss

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

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

These polymorphic type signatures impose no numerical, equality or ordering constraints: the definitions only inspect list or pair structure and apply a supplied function. In particular,

curry (f) x y = f (x, y), uncurry (g) (x, y) = g x y .

The recursive equations describe the two possible list constructors, so they also explain how the empty case terminates each finite computation.

b

i

Solution

In the type signature map :: (u -> v) -> [u] -> [v], the supplied function is concat :: [[a]] -> [a]. Type inference therefore identifies u with [[a]] and v with [a]. Consequently,

map concat :: [[[a]]] -> [[a]]

Thus

[[[α]]] \to [[α]]

is the principal type. For example, map concat [[[1],[2,3]],[[4],[]]] gives [[1,2,3],[4]]: it concatenates each inner group, preserving the outermost grouping.

ii

Solution

Both uses of x in this definition have the same monomorphic type within the body. Write x :: u -> v. The inner application x z forces z :: u and has type v; the outer application x (x z) forces v = u. Thus x :: u -> u. Finally, x (x z) is applied to y, so u must itself be a function type, say a -> b. This gives

f :: ((a -> b) -> a -> b) -> a -> (a -> b) -> b
f x y z = x (x z) y

The principal type is therefore

((α \to β) \to (α \to β)) \to α \to (α \to β) \to β .

The argument x transforms a function into another function of the same type. The body transforms z twice, then applies the resulting function to y; no recursive type equation is required.

c

Solution

Represent Pascal's triangle by an infinite outer lazy list, each of whose elements is one finite row. Pad the preceding row with zero on its left and on its right, then add corresponding entries:

pascal :: [[Integer]]
pascal = iterate next [1]
  where
    -- Padding supplies the two boundary entries as well as the interior sums.
    next :: [Integer] -> [Integer]
    next row = zipWith (+) (0 : row) (row ++ [0])

Here iterate next [1] begins [[1],[1,1],[1,2,1],[1,3,3,1],...]. Every call to next receives a finite row, so its final zero is reachable. Lazy evaluation produces any requested finite prefix without trying to finish the infinite outer list.

Indexing rows and columns from zero, Pascal's rule says

pascal_{n} = [(0 n), (1 n), \dots, (n n)], (j n + 1) = (j - 1 n) + (j n) .

Take out-of-range binomial coefficients to be zero. The seed is the zeroth row, and the padded addition implements this identity at every position, including the two boundaries. Mathematical induction therefore proves every generated row correct. Using unbounded integers prevents overflow. Generating rows zero through

r

takes

Θ (r^{2})

arithmetic operations, with additional bit costs as the binomial coefficients grow.

2

a

Solution

Use structural induction on the finite list xs, strengthening the induction hypothesis to hold for every accumulator value

y

. For the empty list, the defining equation of the left fold gives

x \oplus foldl (\otimes) y [] = x \oplus y = foldl (\otimes) (x \oplus y) [] .

For the inductive step, suppose the identity holds for the tail zs and every accumulator. Expand the first left fold, apply the induction hypothesis at accumulator

y \otimes z

, and then use the supplied compatibility law:

x \oplus foldl (\otimes) y (z : zs) = x \oplus foldl (\otimes) (y \otimes z) zs = foldl (\otimes) (x \oplus (y \otimes z)) zs = foldl (\otimes) ((x \oplus y) \otimes z) zs = foldl (\otimes) (x \oplus y) (z : zs) .

Hence

x \oplus foldl (\otimes) y xs = foldl (\otimes) (x \oplus y) xs .

(3)

Only equation (1) is needed for this part; the seed condition in equation (2) enters the next proof. Quantifying over the accumulator is essential because the recursive call changes it.

b

Solution

Again use structural induction on the finite list. At [], both the right fold and the left fold return the seed

a

. If they agree on zs, then

foldr (\oplus) a (z : zs) = z \oplus foldr (\oplus) a zs = z \oplus foldl (\otimes) a zs = foldl (\otimes) (z \oplus a) zs = foldl (\otimes) (a \otimes z) zs = foldl (\otimes) a (z : zs) .

The third line uses part (a); the fourth uses equation (2). Thus the left-right fold equivalence is

foldr (\oplus) a xs = foldl (\otimes) a xs .

This is a statement about values on finite, total inputs. It does not assert equal evaluation costs or equal behaviour on infinite lists.

c

Solution

Use list concatenation as the combining operation and the empty list as the seed:

concat :: [[a]] -> [a]
concat = foldr (++) []

For three inner lists, this constructs xs ++ (ys ++ (zs ++ [])), preserving the elements' original order. The concise answer is

concat = foldr (+ +) []

d

Solution

Set both

\oplus

and

\otimes

equal to list concatenation, with

a = []

. Associativity gives xs ++ (ys ++ zs) = (xs ++ ys) ++ zs, which is equation (1). The two identity laws give xs ++ [] = [] ++ xs, which is equation (2). Part (b) therefore yields

concat :: [[a]] -> [a]
concat = foldl (++) []

Thus

concat = foldl (+ +) []

on finite lists. The argument order is unchanged: the accumulator is the already concatenated prefix, and the next inner list is appended to its right. This preserves the order but repeatedly copies that prefix.

e

i

Solution

Let there be

k

inner lists, of lengths

ℓ_{1}, \dots, ℓ_{k}

, and let

N = \sum_{j} ℓ_{j}

. Evaluate the whole output list spine, taking each input element as an already available value. The defining equation (x:xs) ++ ys = x : (xs ++ ys) shows that list concatenation traverses its left operand, sharing its right operand.

The right fold puts each original inner list on the left of exactly one concatenation. Thus its total element traversal is proportional to

N

, and visiting the outer list costs

k

T_{right} = Θ (k + N) .

The

k

term matters when many inner lists are empty. With

k

rows each of length

r

, the bound is

Θ (k + k r)

. In particular, with uniformly bounded positive row length it is linear in

k

ii

Solution

Write

S_{j} = ℓ_{1} + \dots + ℓ_{j}

, with

S_{0} = 0

. At the

j

th step of the left fold, the left operand of list concatenation is the accumulated prefix of length

S_{j - 1}

. Fully forcing these concatenations repeatedly copies earlier elements. Including the traversal of the outer list and the whole output spine gives

T_{left} = Θ (k + N + j = 1 \sum k - 1 S_{j}) = Θ (k + N + t = 1 \sum k - 1 (k - t) ℓ_{t}) .

For singleton inner lists, this becomes

Θ (1 + 2 + \dots + (k - 1)) = Θ (k^{2})

, whereas the right fold takes

Θ (k)

. More generally, for equal positive length

r

, the left fold takes

Θ (r k^{2} + k)

O (k N + k)

bound is tight in the worst case over length distributions, but is not a tight formula for every distribution: if all

N

elements occur only in the final inner list, all earlier accumulators are empty and the cost is

Θ (k + N)

. Lazy evaluation changes when the work happens; it does not remove repeated prefix traversal when the whole result is demanded.

3

a

Solution

A word can be a string, and the input text a list of those strings. Use names that avoid clashing with the Standard Prelude machine-word type Word:

type TextWord = String
type Text = [TextWord]

Thus

TextWord = String, Text = [TextWord]

. These are type synonyms, so ordinary string and list operations remain available without wrapping or unwrapping constructors. They describe input that has already been tokenized; punctuation and word boundaries do not need a separate treatment here.

b

Solution

Normalize each word once by applying toLower to its characters. Maintain an association list whose keys are distinct normalized words and whose values are their frequencies:

import Data.Char (toLower)

type TextWord = String
type Text = [TextWord]
type Frequency = Integer
type Entry = (TextWord, Frequency)

count :: Text -> [Entry]
count = foldl addWord [] . map (map toLower)
  where
    -- Increment the unique matching key, or append a new key with count one.
    addWord :: [Entry] -> TextWord -> [Entry]
    addWord [] w = [(w, 1)]
    addWord ((v, n):rest) w
      | w == v    = (v, n + 1) : rest
      | otherwise = (v, n) : addWord rest w

After any input prefix, each normalized word seen so far occurs exactly once as a key, with its number of occurrences as value. This loop invariant holds initially for the empty association list. A step either increments the unique existing entry or introduces exactly one new entry, so mathematical induction proves

lookup w (count input) = Just (number of normalized occurrences of w)

for every word that occurs. In particular, Baa and baa contribute to the same key baa; the three frequency-two keys in the source example are baa, yes and sir.

The association list preserves first-occurrence order, although the specification allows any order here. For

t

input words and

d

distinct normalized words, it performs

O (t d)

key comparisons in the worst case. Character normalization costs the total input character count, and a string comparison can inspect multiple characters. Characterwise toLower supplies the intended case-insensitive comparison convention for the example; full Unicode case folding can require a different normalization policy.

c

Solution

Compare frequencies in decreasing order and use lexicographic order on words to break ties. Implement merge sort explicitly, so no imported sorting routine is needed:

-- Entry, TextWord and Frequency are as in part (b).
before :: Entry -> Entry -> Bool
before (w, p) (v, q) = p > q || (p == q && w <= v)

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

merge :: [Entry] -> [Entry] -> [Entry]
merge [] ys = ys
merge xs [] = xs
merge xa@(x:xs) ya@(y:ys)
  | before x y = x : merge xs ya
  | otherwise  = y : merge xa ys

The merge algorithm step always emits the smaller key under the ordering

(- frequency, word)

. The unchosen heads cannot precede that emitted entry because each input is already sorted. It preserves all entries, and each call removes one head, so it terminates with exactly the sorted union of the inputs. Mathematical induction over the recursive splits establishes correctness of merge sort.

For

n

entries, splitting and merging cost

Θ (n)

per level, and there are

Θ (lo g n)

levels:

T (n) = T (⌊ n /2 ⌋) + T (⌈ n /2 ⌉) + Θ (n) = Θ (n lo g n) (n \geq 2) .

The base cases take constant time. This counts word comparisons as primitive operations, as in the question. If the maximum compared word length is

L

, the character-operation bound becomes

O (L n lo g n)

, in addition to frequency comparison costs.

For the supplied input, sort . count yields

[("baa",2),("sir",2),("yes",2),("any",1),("bags",1),("black",1),
 ("full",1),("have",1),("sheep",1),("three",1),("wool",1),("you",1)]

In particular, the secondary ordering places sir before yes, even though yes appears earlier in the original text. The

Θ (n lo g n)

requirement concerns sort; the simpler association list implementation of count has its own cost.

4

a

Solution

An empty constructor and a constructor containing a label and two subtrees give a polymorphic algebraic data type:

data STree a = Empty | Node (STree a) a (STree a)
  deriving (Eq, Show)

The binary search tree invariant is

every left label < x < every right label

at each Node left x right, together with the same invariant recursively in both subtrees. Labels are distinct because the representation is of a set. The declaration itself needs no ordering constraint; operations that compare labels require Ord a in their type signatures.

b

Solution

Follow the unique branch in which the new key could belong. At an equal key, keep the existing node so that duplicate insertion does not change the represented set:

insert :: Ord a => a -> STree a -> STree a
insert y Empty = Node Empty y Empty
insert y (Node left x right) =
  case compare y x of
    LT -> Node (insert y left) x right
    EQ -> Node left x right
    GT -> Node left x (insert y right)

The Haskell Ord class supplies the three-way comparison. Each visited nonempty node costs one such comparison; rebuilding a node preserves all untouched subtrees. The inserted key satisfies every comparison along its search path, so it obeys both the local and ancestor binary search tree inequalities.

For height of a binary tree

h

, the worst search costs

Θ (h) comparisons

when it reaches the bottom. With

n

existing nodes, a chain can require

n

comparisons, giving a worst case of

Θ (n)

. Under the standard random-insertion model, distinct keys arrive in a uniformly random order and the expected path length is

Θ (lo g (n + 1))

. Thus the usual average-case answer is

Θ (lo g n)

for growing

n

, but this expectation needs the stated distribution: an arbitrary unbalanced binary search tree has no logarithmic guarantee.

c

Solution

A tree fold replaces Empty by a seed and Node by a combining function. The combining function receives the already folded left subtree, the node's label and the already folded right subtree:

foldSTree :: (b -> a -> b -> b) -> b -> STree a -> b
foldSTree combine empty Empty = empty
foldSTree combine empty (Node left x right) =
  combine (foldSTree combine empty left)
          x
          (foldSTree combine empty right)

Its polymorphic type signature is

(β \to α \to β \to β) \to β \to STree α \to β .

The result type need not be the label type: it may be a list, a number or another structure. No ordering constraint is needed because this tree fold follows constructors without comparing labels.

d

Solution

Use the empty list for an empty subtree, and join the left result, the current label and the right result:

flatten :: STree a -> [a]
flatten = foldSTree (\left x right -> left ++ (x : right)) []

Thus

flatten (Node l x r) = flatten (l) + + [x] + + flatten (r)

. This is an inorder traversal. By structural induction, each subtree produces its labels in order; the binary search tree invariant places every left label below

x

and every right label above

x

, proving that the whole result is increasing. The definition works for any binary-tree shape, although its result is sorted only when the ordering invariant holds. Repeated list concatenation can give quadratic cost on a left chain; the question asks for a tree fold definition, rather than an optimal traversal implementation.

e

Solution

An empty binary search tree has zero nodes; a nonempty node contributes one in addition to the sizes of its two subtrees:

size :: STree a -> Integer
size = foldSTree (\left _ right -> 1 + left + right) 0

The answer is

∣ Empty ∣ = 0, ∣ Node l x r ∣ = 1 + ∣ l ∣ + ∣ r ∣

. The tree fold visits every node once, so this takes

Θ (n)

arithmetic operations for

n

nodes.

f

Solution

Count the number of nonempty levels on the longest root-to-leaf branch, taking the empty binary search tree to have depth zero:

depth :: STree a -> Integer
depth = foldSTree (\left _ right -> 1 + max left right) 0

Thus

d (Empty) = 0, d (Node l x r) = 1 + max (d (l), d (r))

. A singleton has depth one under this convention. If height of a binary tree is instead counted in edges, subtract one for a nonempty tree. The complete tree fold takes

Θ (n)

operations.

g

Solution

Search as for insertion. Removing a node with at most one nonempty child leaves that child in its place. With two children, use the smallest key in the right subtree as the replacement and remove that occurrence from the right subtree:

delete :: Ord a => a -> STree a -> STree a
delete _ Empty = Empty
delete y (Node left x right) =
  case compare y x of
    LT -> Node (delete y left) x right
    GT -> Node left x (delete y right)
    EQ -> join left right
  where
    -- Join two search trees with every left key below every right key.
    join :: STree a -> STree a -> STree a
    join Empty r = r
    join l Empty = l
    join l r = let (smallest, rest) = takeMin r
               in Node l smallest rest

-- Precondition: the input tree is nonempty.
takeMin :: STree a -> (a, STree a)
takeMin Empty = error "takeMin: empty tree"
takeMin (Node Empty x right) = (x, right)
takeMin (Node left x right) =
  let (smallest, rest) = takeMin left
  in (smallest, Node rest x right)

The call to takeMin occurs only after both empty cases have been excluded. Its structural recursion follows left children until it reaches the minimum label and rebuilds the path with that occurrence removed.

For a matching label

x

and successor

s

, all left labels are below

x < s

, while every label remaining on the right is strictly above

s

. Thus replacing

x

s

preserves the binary search tree invariant. Every other branch preserves the invariant by structural induction. The resulting set is exactly

keys (delete y t) = keys (t) ∖ {y} .

Whether the key is absent or present, untouched subtrees can be shared. The search path followed by the successor path uses

O (h)

time and fresh nodes for original height of a binary tree

h

, so the worst case is

O (n)

without balancing. This is persistent binary search tree deletion: the original value remains available.

5

a

Solution

A length-zero graph path starts and ends at the same vertex. Therefore

P_{0}

is the Boolean identity matrix. A graph path of length at most one is either such a stationary graph path or one original directed edge:

P_{0} [i, j] = (i = j), P_{1} [i, j] = (i = j) \lor E [i, j], P_{1} = I \lor E .

The logical disjunction is entrywise. Diagonal entries of

E

may be false if there are no self-loops, but every diagonal entry of

P_{1}

is true because the zero-length graph path is allowed.

b

Solution

A graph path of length at most

k + 1

either already has length at most

k

, or consists of a prefix of length at most

k

followed by one edge. Therefore

P_{k + 1} [i, j] = P_{k} [i, j] \lor t = 0 ⋁ n - 1 (P_{k} [i, t] \land E [t, j]) .

The forward implication follows by removing the final edge of a nonempty graph path. Conversely, concatenating the indicated prefix and edge gives a walk of length at most

k + 1

, and removing repetitions if necessary gives a graph path no longer than that walk.

Writing

⊙

for Boolean matrix multiplication, the formula is

P_{k + 1} = P_{k} \lor (P_{k} ⊙ E)

. Because

P_{1}

includes the identity matrix, an equivalent formula is

P_{k + 1} = P_{k} ⊙ P_{1} .

Compute each new matrix from an unchanged copy of the preceding matrix, so the subscript continues to specify exactly the length bound.

c

Solution

Start with

P_{1} = I \lor E

and repeatedly apply part (b), keeping a fresh output matrix. A simple implementation is

P := I OR E
repeat:
    Q := P OR boolean_product(P, E)
    if Q = P: return P
    P := Q

At the start of each iteration,

P = P_{k}

for the current length bound

k

. The update produces

P_{k + 1}

, proving the loop invariant by mathematical induction. If

Q = P

, every edge extension of a known graph path is already known. Repeating the same update then makes no further change, so every longer graph path is represented as well.

Every reachable pair of distinct vertices has a simple path of at most

n - 1

edges: a repeated vertex allows the intervening part to be deleted. Thus the process stabilizes after finitely many updates and returns

R [i, j] = true precisely when j is reachable from i, including i = j .

This is the reflexive transitive closure. An alternative stopping rule is to stop once the length bound is at least

n - 1

, avoiding a final equality-detection iteration. For

n = 0

1

P_{1}

already suffices.

d

Solution

Interpret the source's

m

as the maximum finite shortest-path distance among reachable pairs, taking

m = 0

when only length-zero graph paths are needed. This is the length bound required for reflexive transitive closure. A directed graph cycle permits arbitrarily long walks, so the maximum length of all possible walks would not be a finite termination parameter.^[ref]

For the elementary dense implementation, each Boolean matrix multiplication evaluates all

n^{3}

triples

(i, t, j)

, with no early exit. Each equality test costs

O (n^{2})

. Starting from

P_{1}

, the algorithm reaches

P_{m}

after

m - 1

updates when

m \geq 1

, then performs one further update to detect stability. Consequently, for

n \geq 2

T_{extend} = Θ (n^{3} max {1, m}), auxiliary space = Θ (n^{2}) .

For the usual nontrivial case

m \geq 1

, this is

Θ (m n^{3})

. Since

m \leq n - 1

, the overall worst case is

Θ (n^{4})

. This bound is tight for this implementation: the directed chain

0 \to 1 \to \dots \to n - 1

has

m = n - 1

and gains previously unknown pairs at every length until then, while every update scans all triples. This tightness does not claim an inherent lower bound for the reflexive transitive closure problem; it concerns the specified repeated-extension algorithm.

e

Solution

Split a graph path of length at most

2 k

into two consecutive parts of length at most

k

, allowing a zero-length part. Conversely, concatenating two such parts gives a walk of length at most

2 k

and hence the same reachability. Therefore

P_{2 k} = P_{k} ⊙ P_{k} .

Start at

P_{1} = I \lor E

, then square to obtain

P_{2}, P_{4}, P_{8}, \dots

. Stop at equality of successive matrices, or after the length bound reaches

n - 1

. The invariant is now

P = P_{2^{r}}

after

r

squarings. Equality implies closure under composition, and the included identity matrix ensures reflexivity.

For the same elementary dense Boolean matrix multiplication and equality stopping test, the cost is

T_{square} = Θ (n^{3} (1 + lo g (m + 1))), space = Θ (n^{2}) .

The additive constant covers the final stability check and the cases

m = 0, 1

. Thus, with

m \geq 2

, the number of cubic passes falls from

Θ (m)

Θ (lo g m)

. In terms of

n

alone the worst-case bound improves from

Θ (n^{4})

Θ (n^{3} lo g n)

for these implementations. A directed chain also requires logarithmically many squarings. This comparison uses ordinary triple-loop multiplication, rather than a faster matrix multiplication method.

6

a

Solution

Divide-and-conquer algorithms split a problem into smaller instances of the same kind, solve them recursively, and combine the solutions. A base case handles instances too small to split. For merge sort, divide the input into two halves, recursively sort both halves, and merge them by repeatedly taking the smaller current head. Empty and singleton inputs are already sorted.

The merge algorithm step preserves sortedness because its chosen head is no larger than either remaining head; it also preserves every input occurrence. These facts and mathematical induction on input length prove correctness. Splitting and merging take

Θ (n)

time, so

T (n) = T (⌊ n /2 ⌋) + T (⌈ n /2 ⌉) + Θ (n) = Θ (n lo g n) .

At each level the subproblem sizes sum to

n

, and there are

Θ (lo g n)

levels. Part 3(c) supplies an explicit Haskell implementation of this construction with a more specialized comparison rule. Standard array implementations use

O (n)

auxiliary storage.

b

Solution

Restrict attention to distinct keys; any comparison sort must handle these inputs. A deterministic comparison sort can be represented by a binary decision tree: an internal node records a comparison and its two possible outcomes, and a leaf records the final ordering of the input positions.

There are

n!

possible relative orders. Two different orders cannot finish at the same leaf, since the algorithm would then output the same ordering of positions for both, making at least one result incorrect. A binary decision tree of height

h

has at most

2^{h}

leaves. Hence

2^{h} \geq n!, h \geq ⌈ lo g_{2} (n!)⌉ .

Using the given bound, or just the last

⌊ n /2 ⌋

factors of

n!

, gives

h \in Ω (n lo g n) .

This is a worst-case comparison sorting lower bound, and merge sort achieves the same order. The result concerns comparison sorting; a procedure that uses numerical digits or bounded integer values has a different computational model.

c

i

Solution

Assume

1 \leq i \leq n

. Apply a worst-case

Θ (n lo g n)

comparison sort, such as merge sort or heapsort, to the whole array, then copy its first

i

entries to the output. The copying costs

Θ (i)

, so

T_{1} (n, i) = Θ (n lo g n + i) = Θ (n lo g n) (n \geq 2) .

The comparison sorting lower bound makes the full-sort stage tight. For the sample array, the sorted order begins

2, 6, 7

, which is the required prefix for

i = 3

. This method spends time ordering all

n - i

unreported elements as well.

ii

Solution

Store the array as a binary heap with min-heap order. Build it bottom-up by sifting down internal nodes in reverse order, rather than inserting all

n

values one at a time. The sum of subtree heights is

O (n)

, so construction costs

Θ (n)

. Then perform

i

minimum extractions: output the root, move the last remaining entry to the root, and sift it down to restore the heap order.

Each extraction returns the smallest remaining key, so the outputs are the

i

smallest keys in increasing order. For a heap of current size

s

, an extraction takes

O (lo g (s + 1))

time. Hence

T_{2} (n, i) = O (n + \sum_{j = 0}^{i - 1} lo g (n - j + 1)) = O (n + i lo g n) .

The tight worst-case bound for this ordinary binary heap implementation is

T_{2} (n, i) = Θ (n + i lo g n) .

When the extraction term is substantial, worst-case extractions follow root-to-leaf paths of logarithmic length; when

i

is small, the linear construction already dominates. The bound stays valid at

i = n

, since

lo g (n!) = Θ (n lo g n)

. Building by

n

separate insertions would lose the linear construction bound and is unnecessary.

iii

Solution

Use deterministic median of medians to select the element of rank

i

in worst-case

Θ (n)

time. Partition the array about that value, retaining the

i

smallest elements. The input is a set, so there are no equal-key ambiguities: take the

i - 1

smaller values and the selected value itself. Sort these

i

elements with merge sort, then output them.

For completeness, median of medians groups values in fives, finds each small group's median, recursively selects a median of those medians as a pivot, and recurses only into the partition containing the requested rank. At least

3 n /10 - O (1)

entries lie on each side of the pivot. Its worst-case recurrence is

S (n) \leq S (⌈ n /5 ⌉) + S (7 n /10 + O (1)) + O (n) = O (n) .

Selection and partitioning cost

Θ (n)

, and sorting the retained prefix costs

Θ (i lo g i)

for

i \geq 2

. Including output at

i = 1

gives

T_{3} (n, i) = Θ (n + i lo g (i + 1)) .

Scanning the input is necessary even to identify its minimum. Ordering the selected

i

distinct values also has the comparison sorting lower bound

Ω (i lo g i)

, so this is asymptotically optimal for the task. A usual randomized Quickselect gives linear expected selection time, but its quadratic worst case would not establish the requested worst-case guarantee.

7

a

Solution

Dynamic programming specifies a collection of overlapping subproblems, expresses each answer using smaller subproblem answers, and stores answers so each subproblem is solved once. One may fill a table in dependency order or use memoization to compute only requested entries. The key design choice is a state that retains every feature needed by later decisions.

The principle of optimality says that, after a decision in an optimal solution, the remaining decisions must solve the corresponding residual subproblem optimally. Otherwise, replacing that residual solution by a better one would improve the entire solution. This replacement argument requires the state to describe the residual constraints completely. Its useful form here is

optimal value of a state = feasible first decisions max {immediate value + optimal residual value} .

The maximization applies to these value-maximization problems; minimization uses the analogous minimum recurrence.

b

Solution

In the 0-1 knapsack problem, item

j

has weight

w_{j}

and value

v_{j}

. Choose a subset of the

n

items, using each at most once, whose total weight is at most

W

and whose total value is as large as possible. For the capacity-indexed dynamic program, take

W

and the weights to be nonnegative integers. The empty choice is allowed.

Let

K [j, c]

be the greatest value attainable using only items

1, \dots, j

with capacity

c

. The base case is

K [0, c] = 0

. With item

j

unavailable when it is too heavy, the recurrence is

K [j, c] = {K [j - 1, c], max {K [j - 1, c], v_{j} + K [j - 1, c - w_{j}]}, w_{j} > c, w_{j} \leq c .

Every feasible optimum either excludes item

j

, giving the first candidate, or includes it exactly once, leaving capacity

c - w_{j}

for earlier items. The principle of optimality proves that the remaining earlier items must attain the indicated residual optimum. Conversely, either candidate constructs a feasible solution, so taking the larger is both necessary and sufficient. Mathematical induction on

j

proves the table's meaning and the final answer

K [n, W]

Store item weights and values in arrays and the values in a two-dimensional array with

(n + 1) (W + 1)

entries. Fill rows in increasing

j

; each entry uses at most two values from the previous row. There are

n (W + 1)

constant-work updates, giving

time = Θ (n (W + 1)), table space = Θ ((n + 1) (W + 1)) .

For positive growing capacities this is the familiar

Θ (nW)

bound. The

+ 1

terms also cover capacity zero and zero-weight items: one must not initialize every

K [j, 0]

to zero if zero-weight, positive-value items are allowed.

To recover an actual subset, store the chosen alternative at each entry or compare the two candidates while tracing backward from

(n, W)

. A selected item changes

(j, c)

(j - 1, c - w_{j})

; an excluded item changes it to

(j - 1, c)

. This takes

O (n)

extra time.

If only the optimal value is needed, keep two rows, using

Θ (W + 1)

space. With strictly positive weights, a single capacity row updated in decreasing capacity also prevents item reuse. The two-row version handles zero weights without special in-place reasoning. The running time is pseudopolynomial, since the binary input length of

W

is only logarithmic in its numerical value.

c

Solution

For the two-bag 0-1 knapsack problem, let

D [j, a, b]

be the maximum total value using the first

j

items, with remaining capacity limits

a

in the first bag and

b

in the second. Initialize

D [0, a, b] = 0

. Item

j

has exactly three possible decisions: omit it, place it in bag one if it fits, or place it in bag two if it fits. Hence

D [j, a, b] = max ({D [j - 1, a, b]} \cup {v_{j} + D [j - 1, a - w_{j}, b] : w_{j} \leq a} \cup {v_{j} + D [j - 1, a, b - w_{j}] : w_{j} \leq b}) .

A braced candidate with a false condition is omitted. All candidates refer to layer

j - 1

, which prevents the same item from entering both bags. Combining two independently optimized single-bag knapsacks would not enforce that restriction.

The principle of optimality proves correctness exactly as in part (b): condition on the location of the final item and replace the earlier items by the optimal feasible residual assignment. Every candidate is realizable, and every feasible assignment belongs to one of the three cases. The final answer is

D [n, W_{1}, W_{2}]

Fill the three-dimensional array in increasing item index. Each of its

n (W_{1} + 1) (W_{2} + 1)

updates inspects at most three candidates:

time = Θ (n (W_{1} + 1) (W_{2} + 1)), full space = Θ ((n + 1) (W_{1} + 1) (W_{2} + 1)) .

For positive capacities the customary expression is

Θ (n W_{1} W_{2})

. Keeping only two item layers reduces space to

Θ ((W_{1} + 1) (W_{2} + 1))

for the optimal value. Full decision storage also permits backward reconstruction of each item's bag assignment. Nonnegative integer weights and capacities are the assumptions behind this capacity-indexed dynamic programming table.

8

a

Solution

Use Kahn's algorithm for topological sorting. With an adjacency list representation, count every vertex's indegree by scanning the edges. Put all zero-indegree vertices in a queue. Repeatedly remove one such vertex

u

, append it to the output, and delete its outgoing edges by decrementing the stored indegree of each neighbour; enqueue a neighbour exactly when its count becomes zero.

The loop invariant is that stored counts are the indegrees in the unreported subgraph and the queue contains exactly its unreported zero-indegree vertices. A nonempty finite Directed acyclic graph always has such a vertex: otherwise following incoming edges would eventually repeat a vertex, creating a directed graph cycle. Thus the queue cannot become empty while any vertex remains.

For every original edge

u \to v

v

cannot enter the output until that edge has been removed by outputting

u

. Therefore

u \to v ⟹ position (u) < position (v) .

Each vertex enters and leaves the queue once, and every edge is scanned a constant number of times, giving

Θ (∣ V ∣ + ∣ E ∣)

time and

O (∣ V ∣)

auxiliary space beyond the adjacency lists. If given only an adjacency matrix, scanning neighbours instead takes

Θ (∣ V ∣^{2})

time.

b

Solution

Allow a zero-length graph path, as in Question 5. Then every vertex

a

reaches itself, proving reflexivity. If

a \equiv b

, its definition already includes both directions of reachability, so interchanging

a, b

proves symmetry.

a \equiv b

and

b \equiv c

, concatenate the graph paths

a \to b

and

b \to c

to obtain reachability from

a

c

. Similarly concatenate

c \to b

and

b \to a

for the reverse direction. Repeated vertices can be removed if graph paths are required to be simple. Thus

a \equiv c

, proving transitivity. Consequently

\equiv is an equivalence relation, whose classes are the strongly connected components.

The zero-length convention matters for an isolated vertex: it is still a singleton strongly connected component.

c

Solution

Here the source's unrestricted “cycle” means a closed walk, permitting repeated vertices; part (d) explicitly separates this from a simple cycle.^[ref]

Suppose a closed walk contains both colours. Any two vertices on it reach one another by following suitable portions of the closed walk. All its vertices, and therefore all its edges, lie inside one strongly connected component. That strongly connected component contains internal edges of both colours.

Conversely, suppose one strongly connected component contains a black edge

u \to v

and a white edge

x \to y

. Its strong connectivity supplies a graph path from

v

x

and another from

y

u

, both inside the component. Concatenate

u black v ⇝ x white y ⇝ u .

This is a closed walk containing both chosen edges. Either connecting graph path may have length zero. Thus the mixed-colour closed walk criterion is

a mixed-colour closed walk exists ⟺ some SCC has internal edges of both colours .

The edges must be internal: differently coloured edges merely leaving a strongly connected component do not establish the claim.

d

Solution

Take two directed triangles meeting only at a central vertex

a

. Make

a \to b \to c \to a

entirely black and

a \to d \to e \to a

entirely white. All five vertices lie in one strongly connected component, since every vertex can reach

a

and can be reached from

a

. It contains internal edges of both colours.

A closed walk can traverse the black triangle and then the white triangle. But a simple cycle using edges from both triangles would have to pass through

a

to change triangles and pass through

a

again to return. It would repeat

a

other than the single start/end identification, contradicting simplicity. Removing

a

separates the two triangles, so no other transition between them is possible. Therefore

one SCC can have both edge colours while every simple cycle is monochromatic .

This example avoids self-loops and works even when a directed simple cycle is required to have at least three vertices.

e

Solution

Use the two-pass strongly connected component algorithm. First run a complete depth-first search of

G

, starting a new search at each unvisited vertex as necessary. Append each vertex to a list when its recursive call finishes. Next construct the graph transpose

G^{T}

by reversing every edge. Reset all visited flags. Process the vertices in decreasing first-pass finishing order, running depth-first search in

G^{T}

from each still-unvisited vertex. The newly reached vertices in each such search form one strongly connected component.

To prove this, contract each strongly connected component to one vertex. The resulting condensation graph is a Directed acyclic graph, because a directed graph cycle of distinct components would make them mutually reachable and hence a single component. For a component

C

, write

F (C)

for its largest first-pass finishing time. If there is an edge

C \to D

between distinct components, then

F (C) > F (D)

. Indeed, if the first search reaches

C

before

D

, it can reach

D

, which must finish before the search in

C

finishes. If it reaches

D

first,

D

cannot reach

C

or they would be the same component, so

D

finishes before

C

is discovered.

Among unreported components, the one with greatest

F

therefore has no incoming edge from another unreported component in

G

. In the graph transpose it has no outgoing edge to any other unreported component. A second-pass search cannot escape it, while strong connectivity lets that search reach all its vertices. Earlier reported components are ignored by the visited flags. Repeating this argument proves

each second-pass search returns exactly one SCC, and all SCCs are returned .