Mock Exam 2: Answer Key

Fall 2026, A-I 305. Grade yourself with the rubric lines, then use the table below to decide what to reread. Back to the exam.

Scoring

MCQ key (Questions 8–22)

Question 1 (2 points): DFS, edge types, SCCs

(a) DFS on G, alphabetical

Adjacency lists in alphabetical order: A: B, E. B: C, H. C: A, D. D: E. E: F. F: D. G: H. H: E, G. I: A.

Trace: start at A (pre 1). A→B (2). B→C (3). C→A: A is on the stack, back edge. C→D (4). D→E (5). E→F (6). F→D: D on the stack, back edge. F post 7, E post 8, D post 9, C post 10. Back at B: B→H (11). H→E: E already finished, not a descendant of H, cross edge. H→G (12). G→H: H on the stack, back edge. G post 13, H post 14, B post 15. Back at A: A→E: E already finished and is a descendant of A, forward edge. A post 16. The outer loop skips B–H (all visited) and starts I (17). I→A: A finished, cross edge. I post 18.

Check with the interval rule: for edge \(u \to v\), back if \(v\)’s interval contains \(u\)’s; forward if \(u\)’s contains \(v\)’s (non-tree); cross if \(v\)’s interval ends before \(u\)’s starts. H→E: E = [5,8], H = [11,14], so cross. Decreasing post in G: I, A, B, H, G, C, D, E, F.

(b) SCC algorithm

Reverse graph \(G^R\), adjacency in alphabetical order: A: C, I. B: A. C: B. D: C, F. E: A, D, H. F: E. G: H. H: B, G. I: (none).

DFS on \(G^R\): A (1) → C (2) → B (3); B→A visited; B post 4, C post 5. A→I (6), I post 7. A post 8. Outer loop: B, C done; D (9) → C visited; D→F (10) → E (11); E→A, E→D visited; E→H (12); H→B visited; H→G (13); G→H visited; G post 14, H 15, E 16, F 17, D 18.

Decreasing post in \(G^R\): D, F, E, H, G, A, I, C, B. Now explore \(G\) in that order:

1. explore(D) in G reaches D, E, F. SCC 1 = {D, E, F}.
2. F, E done. explore(H) reaches H, G (E is done). SCC 2 = {G, H}.
3. G done. explore(A) reaches A, B, C (E, H done). SCC 3 = {A, B, C}.
4. explore(I): SCC 4 = {I}.

Order found: {D,E,F}, {G,H}, {A,B,C}, {I}. Each one is a sink of what remains, which is why the algorithm works.

(c) Sources, sinks, metagraph

Source SCC: {I} (nothing enters I). Sink SCC: {D,E,F} (no edge leaves D, E, F). {A,B,C} and {G,H} are neither.

(d) Edges to add

Answer: 1. Example: add D→I (any edge from a vertex of {D,E,F} to I).

Justification: G is not strongly connected, so at least 1 edge is needed. One is enough: the metagraph has exactly one source {I} and one sink {D,E,F}. Every vertex is reachable from I (I→A→B→C, B→H→G, C→D→E→F), and every vertex can reach {D,E,F} (A, B, C via C→D; G, H via H→E; I via A). After adding D→I, any \(u\) reaches \(v\) by \(u \to \cdots \to D \to I \to \cdots \to v\). In general the answer is max(#source SCCs, #sink SCCs) for a graph that is not strongly connected; here max(1, 1) = 1.

Question 2 (2 points): Dijkstra

(a) Trace

Iteration 0 is the initialization; iteration \(i\) shows dist after the \(i\)-th deleteMin and its edge updates. Removal order: S, B, A, C, D, E, F.

Key updates: removing B lowers A from 4 to 3 (1 + 2) and sets C = 6, E = 10. Removing A lowers C to 4 and sets D = 9. Removing C lowers D to 6 (C→E gives 11, no change). Removing D lowers E to 7 and sets F = 11. Removing E lowers F to 9. No ties occur at any deleteMin.

(b) Shortest-path tree

prev pointers: S→B, B→A, A→C, C→D, D→E, E→F. The tree is a single path S → B → A → C → D → E → F with distances 0, 1, 3, 4, 6, 7, 9.

(c) Dijkstra fails with a negative edge (Quiz 6)

Dijkstra removes S, sets A = 2 and B = 3, then removes A (2 < 3) and declares dist(A) = 2 final. Dijkstra outputs dist(A) = 2. The truth is dist(A) = 1 via S→B→A (3 − 2). The negative edge out of B is seen only after A was already finalized.

Side note: if your Dijkstra code still relaxes edges into vertices already removed from the heap, A’s label changes to 1 late, but A was already output and anything computed from it is stale. Adding A→C 1 shows this: C stays at 3 while the truth is 2 (checked by script). On the exam, state the version you use: once a vertex is removed, it is final.

Question 3 (2 points): Counting shortest paths; DPV 4.8

(a) Algorithm

Run Dijkstra and carry a count with each vertex. Same pattern as Exercise 4.15 (usp) and 4.18 (best) from lecture: on a strict improvement, overwrite; on a tie, combine.

for all u ∈ V
    dist[u] = ∞
    count[u] = 0
dist[s] = 0
count[s] = 1
H = MakeQueue(V)
while (H is not empty)
    u = deleteMin(H)
    for all edges (u, v) ∈ E
        if dist(v) > dist(u) + ℓ(u, v)
            dist(v) = dist(u) + ℓ(u, v)
            count[v] = count[u]
            DecreaseKey(H, v)
        else if dist(v) = dist(u) + ℓ(u, v)
            count[v] = count[v] + count[u]

Correctness. Every shortest path to \(v \ne s\) ends with an edge \((u, v)\) where \(u\) is a tight predecessor: \(\text{dist}(u) + \ell(u,v) = \text{dist}(v)\). So the true count is $$\#\text{paths}(v) = \sum_{u \text{ tight for } v} \#\text{paths}(u).$$ Because all lengths are positive, every tight predecessor has \(\text{dist}(u) < \text{dist}(v)\), so it is removed from the heap before \(v\). By induction on removal order, count[u] is already final when \(u\) is removed and its edge \((u, v)\) is examined (exactly once). When the edge from \(u\) gives a strictly better distance, every count collected so far came from paths that are not shortest, so we overwrite. When it ties, we add. After the last tight predecessor is processed, count[v] equals the sum above, and nothing changes it later (a vertex removed after \(v\) has dist \(\ge\) dist(\(v\)), so its edge into \(v\) can’t be tight). Unreachable vertices keep count 0.

Running time. Dijkstra plus \(O(1)\) extra work per edge: \(O((|V| + |E|) \log |V|)\) with a binary heap.

Tiny check. S→A 1, S→B 1, A→C 1, B→C 1, C→D 2: count[C] = 1 + 1 = 2 (second update is a tie), count[D] = count[C] = 2.

(b) Professor Lake (DPV 4.8): not valid

Original: the shortest path from \(u\) to \(w\) is \(u \to v \to w\) with length \(-2 + 2 = 0\), better than the direct edge (2). Add 3 to every edge: lengths become 1, 5, 5. Now \(u \to v \to w\) costs 6 and \(u \to w\) costs 5, so Dijkstra returns \(u \to w\), which has length 2 in the original graph, not 0. Wrong. Reason: adding \(c\) to every edge adds \(k \cdot c\) to a path with \(k\) edges, so paths with more edges are penalized more and the ranking of paths changes.

Question 4 (3 points): MST

(a) MST cost

12: edges AC 1, FG 1, BD 2, DE 2, AB 3, EF 3 (1 + 1 + 2 + 2 + 3 + 3).

(b) Number of MSTs

2. After the four weight-1 and weight-2 edges, the components are {A, C}, {B, D, E}, {F, G}. Joining {A, C} to {B, D, E}: the cheapest crossing edges are AB 3 and BC 3, a tie, so either works. Joining {F, G} to the rest: EF 3 is the unique cheapest (EG 4, DF 6, BF 7). The weight-1 and weight-2 edges are each forced (no ties that close different cycles). So the MSTs are {AC, FG, BD, DE, AB, EF} and {AC, FG, BD, DE, BC, EF}, both cost 12.

(c) Kruskal with justifying cuts

Sorted edges (ties alphabetical): AC 1, FG 1, BD 2, DE 2, AB 3, BC 3, EF 3, CD 4, EG 4, CE 5, DF 6, BF 7.

Order added: AC(1), FG(1), BD(2), DE(2), AB(3), EF(3). Six edges for seven vertices, so stop. In every row, \(X\) (edges chosen so far) does not cross the cut, which the cut property requires.

(d) Prim from A

Order vertices are added: A, C, B, D, E, F, G. Iteration 0 is the initialization; iteration \(i\) shows cost after the \(i\)-th deleteMin.

Prim’s edges (prev pointers): AB, AC, BD, DE, EF, FG, cost 12. When C is added, BC (3) ties B’s current cost 3, so B keeps prev = A.

Question 5 (2 points): Huffman; MST true/false

(a) Huffman code

Repeatedly merge the two smallest frequencies in the current list:

1. f (5) + e (8) → 13. List: 32, 25, 20, 10, 13.
2. d (10) + {f,e} (13) → 23. List: 32, 25, 20, 23.
3. c (20) + {d,f,e} (23) → 43. List: 32, 25, 43.
4. b (25) + a (32) → 57. List: 43, 57.
5. 43 + 57 → 100 (root).

              (100)
          0 /       \ 1
        (43)         (57)
      0 /  \ 1     0 /  \ 1
       c   (23)     b    a
       20  0/ \1    25   32
           d  (13)
           10 0/ \1
              f   e
              5   8

Bits per 100 characters: \(32 \cdot 2 + 25 \cdot 2 + 20 \cdot 2 + 10 \cdot 3 + 8 \cdot 4 + 5 \cdot 4 = 64 + 50 + 40 + 30 + 32 + 20 = \mathbf{236}\). Check: the sum of the internal node weights, \(13 + 23 + 43 + 57 + 100 = 236\). A fixed-length code for 6 symbols needs \(\lceil \log_2 6 \rceil = 3\) bits each, so \(\mathbf{300}\) bits. Huffman saves 64 bits per 100 characters.

Your 0/1 labels may differ (any swap of children is fine). The lengths must be a = 2, b = 2, c = 2, d = 3, e = 4, f = 4.

(b) True or false (DPV 5.9)

1. TRUE. Suppose \(e\) is in an MST \(T\). Removing \(e\) splits \(T\) into two parts; the rest of the cycle must cross between them on some other edge \(e'\), which is lighter than \(e\). Then \(T - e + e'\) is a lighter spanning tree, a contradiction.
2. FALSE. Triangle a–b 2, b–c 2, a–c 3. The shortest a–c path is the edge a–c (3 < 2 + 2 = 4), but the only MST is {ab, bc} (cost 4), which does not contain a–c.
3. TRUE. Let \(e = (u, v)\). Take the cut \(S = \{u\}\) with \(X = \emptyset\). \(e\) crosses it, and no edge in the graph is lighter, so \(e\) is a lightest crossing edge. The cut property puts \(e\) in some MST.

Question 6 (2 points): 0/1 knapsack

(a) Recurrence

\(B[0, w] = 0\) for all \(w\) (no items). For \(k \ge 1\), with item \(k\) having weight \(w_k\) and value \(v_k\):

Skip item \(k\), or take it once and use the remaining capacity on items \(1..k-1\). Time \(O(nW)\).

(b) Table

(c) Optimum

16, using items 2 and 4 (weight 6 + 2 = 8, value 13 + 3 = 16). Traceback: \(B[4,8] = 16 \ne B[3,8] = 15\), so item 4 is taken; go to \(B[3, 6] = 13 = B[2, 6]\), so item 3 is not; \(B[2,6] = 13 \ne B[1,6] = 7\), so item 2 is taken; go to \(B[1, 0] = 0\), so item 1 is not.

(d) Greedy by value/weight

Ratios: item 1: 7/3 ≈ 2.33, item 2: 13/6 ≈ 2.17, item 3: 2/1 = 2, item 4: 3/2 = 1.5. Greedy takes item 1 (weight 3), skips item 2 (3 + 6 = 9 > 8), takes item 3 (weight 4), takes item 4 (weight 6). Value 7 + 2 + 3 = 12 < 16: not optimal. (Greedy by ratio is optimal only for fractional knapsack.)

(e) With repetition

\(K(w) = \max_{i : w_i \le w} \{ K(w - w_i) + v_i \}\), \(K(0) = 0\).

K(8) = 18, e.g. item 1 twice and item 3 twice (weight 3 + 3 + 1 + 1 = 8, value 7 + 7 + 2 + 2 = 18).

Question 7 (2 points): Yuckdonald’s (DPV 6.3)

(a) Algorithm

• Subproblem. \(P(i)\) = maximum total profit using only locations \(1, \ldots, i\).
• Helper. \(\text{prev}(i)\) = the largest \(j < i\) with \(m_j \le m_i - k\) (0 if none): the last location still allowed if we open at \(i\).
• Recurrence. Either skip location \(i\), or open there and use only locations up to prev(\(i\)): $$P(i) = \max\{\, P(i-1),\; p_i + P(\text{prev}(i)) \,\}.$$
• Base case. \(P(0) = 0\).
• Order. \(i = 1, 2, \ldots, n\) (each entry uses only smaller indices).
• Answer. \(P(n)\). Trace back to get the locations: at \(i\), if \(P(i) \ne P(i-1)\), open at \(i\) and jump to prev(\(i\)); otherwise go to \(i - 1\).
• Running time. Computing each prev(\(i\)) by scanning back is \(O(n)\), so \(O(n^2)\) total. Since the \(m_i\) are sorted, prev(\(i\)) never decreases, so one pointer that only moves forward finds all of them in \(O(n)\) total, giving \(O(n)\).

P[0] = 0
j = 0
for i = 1 to n
    while (j + 1 < i and m[j+1] ≤ m[i] − k)
        j = j + 1
    prev[i] = j
    P[i] = max(P[i−1], p[i] + P[prev[i]])
return P[n]

(b) Run on the instance

prev = [0, 0, 1, 3, 3, 4], P = 0, 5, 6, 9, 18, 18, 25. Maximum profit 25, using locations 1, 3, 4, 6 (miles 1, 4, 7, 10; profits 5 + 4 + 9 + 7). Traceback: P(6) ≠ P(5), open 6, jump to 4; P(4) ≠ P(3), open 4, jump to 3; P(3) ≠ P(2), open 3, jump to 1; P(1) ≠ P(0), open 1.

← Back to Mock Exam 2