Algorithm design and analysis

Two sorted lists have lengths $5$ and $7$. What is the largest number of comparisons the merging procedure can need to merge them?

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?

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)$.

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?

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$?

In the proof of Theorem 5 (Dijkstra), which step uses the hypothesis that all edge weights are non-negative?

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?

What is the length of a longest common subsequence of AGGTAB and GXTXAYB?

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₂.)

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.