Algorithms Practice Exam — Free

This recurrence has the Master Theorem form $T(n) = aT(n/b) + f(n)$ with $a = 2$, $b = 4$ and $f(n) = n^{1/2}$. The critical exponent is

so $n^{\log_b a} = n^{1/2}$, exactly the same growth as $f(n)$. That is case 2 (the work at every level matches the work at the leaves), which gives $T(n) = \Theta(n^{\log_b a}\log n) = \Theta(\sqrt{n}\log n)$.

Unrolling the recursion confirms it. At depth $k$ there are $2^k$ subproblems, each of size $n/4^k$ and cost $\sqrt{n/4^k} = \sqrt{n}/2^k$, so each level costs $2^k\cdot\sqrt{n}/2^k = \sqrt{n}$. There are $\log_4 n$ levels before the size reaches 1, so the total is $\sqrt{n}\log_4 n$ plus $2^{\log_4 n} = \sqrt{n}$ for the leaves, which is $\Theta(\sqrt{n}\log n)$. Numerically, for $n = 4^{10}$ the exact solution is $\sqrt{n}\,(\log_4 n + 1) = 1024\times 11 = 11\,264$, whereas $\sqrt{n}$ alone is only 1024.

Option A is the tempting answer: it is what you get by assuming the root or the leaves dominate (cases 3 and 1), but here every level does equal work, and $\log n$ equal levels add a factor of $\log n$. Options C and D would require $f(n)$ to grow polynomially faster than $\sqrt{n}$, which it does not.

$T(n) = \Theta(\sqrt{n}\log n)$ (option B).

Kruskal's algorithm sorts the edges by weight and adds each edge whose endpoints lie in different components (checked with union-find), skipping any edge that would close a cycle.

Sorted edges: A–C (1), E–F (2), A–B (3), D–F (4), B–D (5), B–C (7), C–E (8), D–E (9), C–D (12).

• A–C (1): components {A, C}. Add.
• E–F (2): {A, C}, {E, F}. Add.
• A–B (3): B joins A's component: {A, B, C}, {E, F}. Add.
• D–F (4): D joins F's component: {A, B, C}, {D, E, F}. Add.
• B–D (5): merges the two components into {A, B, C, D, E, F}. Add.

Five edges now connect six vertices, which is $|V| - 1$, so the tree is complete and the algorithm can stop. The next edge, B–C (7), is the first one examined and rejected: B and C are already connected (through A), so adding it would form a cycle. C–E, D–E and C–D are rejected for the same reason.

Total weight: $1+2+3+4+5 = 15$.

Because all edge weights are distinct, the minimum spanning tree is unique, and Prim's algorithm started from A confirms it: it picks A–C (1), then A–B (3), then B–D (5), then D–F (4), then F–E (2), the same five edges.

Edges added: A–C, E–F, A–B, D–F, B–D; total weight 15; B–C (7) is the first edge rejected.

(a) In an optimal way of making $x$, the last coin has value $d \in \{1, 4, 6\}$, and removing it must leave an optimal way of making $x - d$ (otherwise swapping in a better one would improve the total). This optimal substructure gives

(b) Fill the table in increasing $x$, using only entries already computed:

For example $c(4) = 1 + \min(c(3), c(0)) = 1$, $c(8) = 1 + \min(c(7), c(4), c(2)) = 1 + 1 = 2$, $c(10) = 1 + \min(c(9), c(6), c(4)) = 2$, and $c(14) = 1 + \min(c(13), c(10), c(8)) = 1 + \min(3, 2, 2) = 3$.

(c) $c(14) = 3$. Trace back through the choices: $c(14)$ came from $c(8)$ with a 6 (or equally from $c(10)$ with a 4), $c(8)$ from $c(4)$ with a 4, and $c(4)$ from $c(0)$ with a 4. The coins are 6 + 4 + 4 = 14. No two coins can reach 14, since the largest two sum to 12, so 3 is indeed optimal.

(d) Greedy takes 6, then another 6 (leaving 2), then 1 and 1: four coins, 6 + 6 + 1 + 1. The dynamic-programming solution uses three, so greedy is not optimal for this coin system. It fails because taking the second 6 leaves a remainder (2) that only the 1-coins can cover, whereas giving up one 6 for two 4s covers the remainder exactly.

$c(x) = 1 + \min\{c(x-1), c(x-4), c(x-6)\}$ with $c(0) = 0$; $c(14) = 3$ using coins 6, 4, 4; greedy needs 4 coins.