Each worksheet prints cleanly on A4 or Letter. Answer keys are on a separate page.

The Lumenary · Early undergraduate

Algorithm design and analysis

Name: ______________________

Date: ______________________

You will learn to

Design divide-and-conquer algorithms and analyse them with recurrences, proving that mergesort is correct and makes at most $n\lceil\log_2 n\rceil$ comparisons
Prove that every comparison sort needs at least $\log_2 n! = \Theta(n \log n)$ comparisons in the worst case
Prove the correctness of greedy algorithms by exchange arguments — Kruskal's algorithm via the cut property, and Dijkstra's algorithm when all edge weights are non-negative — and recognise when greedy choice fails
Design dynamic-programming algorithms from an optimal-substructure recurrence, as for the longest common subsequence, and analyse their cost
Use breadth-first search for unweighted distances and choose an appropriate algorithm for a graph problem

1.
Two sorted lists have lengths $5$ and $7$ . What is the largest number of comparisons the merging procedure can need to merge them?
2.
What is the decision-tree lower bound $\lceil \log_2 n! \rceil$ on the worst-case number of comparisons needed to sort $n = 5$ distinct items?
3.
Mergesort's worst-case comparison count satisfies $C(1) = 0$ and $C(n) = 2C(n/2) + n - 1$ for $n$ a power of two. Compute $C(8)$ .
4.
The network of towns in the Explore section has these cable costs: $AB = 4$ , $AC = 1$ , $BC = 2$ , $BD = 5$ , $CD = 8$ , $CE = 10$ , $DE = 3$ . Run Kruskal's algorithm. What is the total cost of the minimum spanning tree?
5.
Run Dijkstra's algorithm from $s$ on the directed graph with edges $s \to a$ (weight $1$ ), $s \to b$ (weight $2$ ) and $b \to a$ (weight $-2$ ). What does it report for $a$ ?
- A. $1$ — which is wrong, since the path $s \to b \to a$ has weight $0$ .
- B. $0$ , the correct distance.
- C. $-2$
- D.It detects the negative edge and stops with an error.
6.
In the proof of Theorem 5 (Dijkstra), which step uses the hypothesis that all edge weights are non-negative?
- A. $\delta(s, y) \le \delta(s, u)$ , because $y$ lies on a shortest path to $u$ .
- B. $d(y) \le d(x) + w(x, y)$ .
- C. $d(u) \le d(y)$ .
- D. $\delta(s, x) + w(x, y) = \delta(s, y)$ .
7.
Suppose a currency has coins worth $1$ , $4$ and $5$ . For which amount does the greedy method (always use the largest coin that fits) not use the fewest coins?
- A. $8$
- B. $9$
- C. $10$
- D. $7$
8.
What is the length of a longest common subsequence of AGGTAB and GXTXAYB?
9.
Which specification correctly says that a Lean function sort : List ℕ → List ℕ is a sorting function? (Sorted l means each entry is ≤ the later ones; l₁ ~ l₂ means l₁ is a permutation of l₂.)
- A.∀ l, Sorted (sort l) ∧ sort l ~ l
- B.∀ l, Sorted (sort l)
- C.∀ l, sort l ~ l
- D.∀ l, Sorted (sort l) ∧ (sort l).length = l.length
10.
Write lcs_length(x, y) that returns the length of a longest common subsequence of the strings x and y, by filling the dynamic-programming table of Theorem 6 in $O(mn)$ time.
Computational — Practice

Answer key — Algorithm design and analysis

1.
Each comparison sends one item to the output, and when one list is empty the rest is copied with no comparisons. At least one item (the last) is placed without a comparison, so at most $5 + 7 - 1 = 11$ comparisons are made. The bound is reached when the two largest items lie in different lists, for example $1, 2, 3, 4, 12$ and $5, 6, \dots, 11$ : four comparisons place $1, 2, 3, 4$ , seven more place $5, \dots, 11$ (each compared with $12$ ), and $12$ is copied at the end.
2.
The tree needs at least $5! = 120$ leaves, and a tree of height $h$ has at most $2^h$ leaves. Since $2^6 = 64 < 120 \le 128 = 2^7$ , the height is at least $7$ . (Seven comparisons do suffice for five items — the 'merge insertion' method of Lester Ford and Selmer Johnson, 1959, achieves this — while mergesort uses $8$ .) The Lean theorem five_items_need_seven proves the bound.
3.
$C(2) = 1$ , $C(4) = 2 \cdot 1 + 3 = 5$ , $C(8) = 2 \cdot 5 + 7 = 17$ . In general $C(2^k) = k\,2^k - 2^k + 1$ (check: $3 \cdot 8 - 8 + 1 = 17$ ), a little below the bound $n \log_2 n = 24$ ; the lower bound is $\lceil \log_2 8! \rceil = \lceil \log_2 40320 \rceil = 16$ .
4.
In order of cost: take $AC (1)$ , $BC (2)$ , $DE (3)$ ; skip $AB (4)$ , since $A$ and $B$ are already joined through $C$ ; take $BD (5)$ , which joins $\{A, B, C\}$ to $\{D, E\}$ . Now there are $4$ edges, a spanning tree of cost $1 + 2 + 3 + 5 = 11$ . By Theorem 4 it is a minimum spanning tree.
5.
Dijkstra finishes $s$ ( $d = 0$ ), then $a$ ( $d(a) = 1$ , the smaller tentative value), then $b$ ( $d(b) = 2$ ). Relaxing $b \to a$ would give $0$ , but $a$ is already finished. So it reports $1$ , while the true distance is $0$ . The proof of Theorem 5 breaks at the step $\delta(s, y) \le \delta(s, u)$ , which needs non-negative weights.
6.
The chain is $d(y) \le d(x) + w(x, y) = \delta(s, y) \le \delta(s, u) \le d(u) \le d(y)$ . Only $\delta(s, y) \le \delta(s, u)$ uses non-negativity: it says the rest of the shortest path, from $y$ to $u$ , cannot have negative weight. The counterexample in the previous exercise breaks exactly there.
7.
For $8$ , greedy takes $5$ , then three $1$ s: four coins, while $4 + 4$ takes two. For $7$ , $9$ and $10$ greedy is optimal. As for coins $1, 3, 4$ , the form of the greedy algorithm says nothing about its correctness; dynamic programming ( $m(x) = 1 + \min_c m(x - c)$ ) always finds the optimum.
8.
GTAB is a common subsequence: in AGGTAB take G (position 2), T (4), A (5), B (6); in GXTXAYB take G (1), T (3), A (5), B (7). No common subsequence is longer: the letters X and Y do not occur in AGGTAB, so a common subsequence uses only letters of GXTXAYB from G, T, A, B, and each of these occurs there only once — at most $4$ letters. The dynamic-programming table confirms $L(6, 7) = 4$ .
9.
Only (a) is right. (b) is satisfied by the constant function [], (c) by the identity, and (d) by a function that outputs the right number of zeros. Writing a specification forces you to say what correctness means — the same two properties, sortedness and permutation, that the lemma and Theorem 1 prove for mergesort.
10.
```
def lcs_length(x, y):
    m, n = len(x), len(y)
    L = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])
    return L[m][n]
```
Each of the $(m+1)(n+1)$ entries is computed once, in constant time, from entries already filled in, so the running time is $O(mn)$ . The last test uses strings of length $140$ and $120$ : the plain recursion would never finish, but the table has only about $17\,000$ cells. Correctness is Theorem 6 (and the Lean theorems lcs_optimal and lcs_achieved).