3 · Greedy algorithms

DPV Ch 5 + lectures 21–26 + HW4 P2–P5. Two exam problems come from here. Expect a hand trace (Kruskal / Prim / union-find / Huffman), a true/false-with-proof item like DPV 5.9, or "prove it or give a counterexample".

Router

1 · The greedy template and how to prove it

sort candidates by some rule
S = ∅
for each candidate c, in that order:
    if S ∪ {c} is feasible: S = S ∪ {c}
return S

Greedy is correct only when both hold:

• Greedy-choice property: some optimal solution contains the greedy first choice.
• Optimal substructure: after the greedy choice, what is left is a smaller instance of the same problem, and an optimal answer to it extends to an optimal answer overall.

DP also needs optimal substructure. The greedy-choice property is what lets greedy commit to one choice instead of trying all of them.

2 · Fractional knapsack

Do: compute value \(v_i = b_i / w_i\), sort decreasing, take whole items until the next one does not fit, then take a fraction of it. \(O(n \log n)\).

Lecture example, \(W = 10\):

• By value: item 5 (1 g, 50), item 3 (2 g, 40), item 4 (6 g, 30), then 1 g of item 2 (4). Total \(50 + 40 + 30 + 4 = \mathbf{124}\), optimal.
• Wrong rule, increasing weight: 5, 3, 1, half of 4: \(50 + 40 + 12 + 15 = 117\).
• Wrong rule, decreasing benefit: 5, 3, then 7/8 of item 2: \(50 + 40 + 28 = 118\).

Proof (exchange, by contradiction). Let \(x_i\) be the amount of item \(i\) taken. Suppose some solution beats greedy. Then there are items \(i, j\) with \(v_i > v_j\), \(x_j > 0\), and \(x_i < w_i\): it uses some of a lower-value item while a higher-value item is not used up. Let \(y = \min\{w_i - x_i,\ x_j\}\). Replace \(y\) grams of \(j\) by \(y\) grams of \(i\). Weight is unchanged and benefit rises by \(y(v_i - v_j) > 0\), so that solution was not optimal. Contradiction.

0/1 knapsack: greedy by value fails

• Lecture (\(W = 9\); items (w, b) = (4,20), (2,3), (2,6), (6,25), (2,80)): greedy by value takes 5, then 1 (weight 6, benefit 100); item 4 does not fit, so greedy stops at 100. Optimum is items 1, 3, 5 = 106. (DP table on page 4.)
• Smallest version: \(W = 4\), items (3, 5), (2, 3), (2, 3). Greedy by value takes (3, 5) and nothing else fits: 5. The two small items give 6.
• Deck: \(W = 50\), gold (10, $60), silver (20, $100), bronze (30, $120). Fractional greedy = $240. 0/1 greedy = gold + silver = $160. 0/1 optimum = silver + bronze = $220.

Why the proof breaks: the exchange swaps weight unit-for-unit. In 0/1 you cannot take \(y\) grams of an item, so the swap is not available. 0/1 knapsack needs DP in \(O(nW)\).

3 · Activity selection (interval scheduling)

Do: sort by finish time; take an activity if it starts at or after the last chosen finish. \(O(n \log n)\).

ActivitySelect(s, f):
    sort activities so f1 ≤ f2 ≤ … ≤ fn
    S = {a1}; last = f1
    for i = 2 to n:
        if si ≥ last: S = S ∪ {ai}; last = fi
    return S

Deck example: A 8–21, B 9–13, C 12–14, D 13–17, E 16–18, F 17–21, G 21–22. By finish: B (13), C (14, starts 12 < 13, skip), D (17, starts 13 ✓), E (18, starts 16 < 17, skip), A (21, skip), F (21, starts 17 ✓), G (22, starts 21 ✓). Result {B, D, F, G}, 4 activities. Brute force confirms 4 is the maximum.

Proof sketch. Let \(g_1\) be the activity that finishes first and \(O = \{o_1, \dots, o_k\}\) an optimal schedule sorted by finish time. Swap: \(O' = O - \{o_1\} \cup \{g_1\}\). Every \(o_j\) with \(j \ge 2\) starts at or after \(f(o_1) \ge f(g_1)\), so \(O'\) is feasible, with \(k\) activities, so it is optimal. What remains is the same problem on \(\{a : s(a) \ge f(g_1)\}\), which contains \(O' - \{g_1\}\) (size \(k-1\)). By induction greedy picks \(k - 1\) there. Total \(k\).

Rules that fail (each counterexample checked):

• Earliest start: [0,10], [1,2], [3,4]. Greedy takes [0,10] only (1); optimum 2.
• Shortest duration: [1,5], [4,7], [6,10]. Greedy takes [4,7], which overlaps both others (1); optimum [1,5], [6,10] (2).
• Weighted version: earliest finish ignores weights. Use DP (weighted interval scheduling, page 4).

4 · Minimum spanning trees

Facts used in every proof: a tree on \(n\) vertices has \(n - 1\) edges; any connected graph with \(n - 1\) edges is a tree; removing a tree edge splits the tree into two components; adding a non-tree edge creates exactly one cycle.

Cut property

Proof (lecture). \(X \subseteq T\) for some MST \(T\). If \(e \in T\), done. Otherwise add \(e\) to \(T\): this creates a cycle. The cycle crosses the cut at \(e\), so it must cross back at some other edge \(e'\). Let \(T' = T \cup \{e\} - \{e'\}\). \(T'\) is connected with \(n - 1\) edges, so it is a tree. \(e' \notin X\) because no edge of \(X\) crosses the cut, so \(X \cup \{e\} \subseteq T'\). And $$\text{weight}(T') = \text{weight}(T) + w(e) - w(e') \le \text{weight}(T)$$ since \(e\) is a lightest crossing edge. So \(T'\) is also an MST.

With distinct weights, the lightest edge across any cut is in every MST (the swap would give a strictly lighter tree).

Kruskal + union-find

Do: sort edges; add the next lightest edge that does not form a cycle. Each added edge joins two components, so it is the lightest edge across the cut (one of those components, rest of graph). That is why it is safe.

procedure kruskal(G, w)
for all u ∈ V: makeset(u)
X = {}
sort the edges E by weight
for all edges {u, v} ∈ E, in increasing order of weight:
    if find(u) ≠ find(v):
        add edge {u, v} to X
        union(u, v)

procedure makeset(x)
    π(x) = x
    rank(x) = 0

function find(x)                     (with path compression)
    if x ≠ π(x): π(x) = find(π(x))
    return π(x)

procedure union(x, y)                (union by rank)
    rx = find(x); ry = find(y)
    if rx = ry: return
    if rank(rx) > rank(ry): π(ry) = rx
    else:
        π(rx) = ry
        if rank(rx) = rank(ry): rank(ry) = rank(ry) + 1

• Union by rank: \(\text{rank}(x) < \text{rank}(\pi(x))\); a root of rank \(k\) has at least \(2^k\) nodes; so trees have height \(\le \log n\) and find is \(O(\log n)\).
• Path compression: every node on the find path is re-pointed straight at the root. Ranks are not changed. Amortized cost per operation becomes \(O(\log^* n)\).
• Kruskal running time: sort \(O(m \log m) = O(m \log n)\) (since \(m \le n^2\)), plus \(2m\) finds and \(n - 1\) unions at \(O(\log n)\) each. Total \(O(m \log n)\).

Prim

Do: grow one tree \(S\). Each step adds the vertex outside \(S\) with the smallest \(\text{cost}(v) = \min_{u \in S} w(u, v)\). It is Dijkstra with a different key, so it has the same running time, \(O((n + m)\log n)\) with a binary heap.

procedure prim(G, w)
for all u ∈ V:
    cost(u) = ∞
    prev(u) = nil
pick any initial node u0
cost(u0) = 0
H = makequeue(V)            (priorities are cost values)
while H is not empty:
    v = deletemin(H)
    for each {v, z} ∈ E:
        if z ∈ H and cost(z) > w(v, z):
            cost(z) = w(v, z)
            prev(z) = v
            decreasekey(H, z)

Trap: Dijkstra uses dist(v) + w(v, z). Prim uses w(v, z) alone. Prim is correct with negative edges (it only relies on the cut property); Dijkstra is not.

Worked: DPV 5.1

(a) MST cost = 19. (b) 2 MSTs: {AE, EF, FG, GH, CG, DG} plus either BE or BF (both weight 2). (c) Kruskal order (ties alphabetical) with a justifying cut. The cut is the current component of one endpoint vs the rest; the added edge is a lightest edge crossing it.

Total \(1 + 1 + 2 + 3 + 3 + 4 + 5 = 19\). (The other endpoint's component also works as a cut every time; a script checked both.)

Worked: DPV 5.2

(a) Prim from A, alphabetical ties. Removal order A, B, C, G, D, F, H, E. Cost array after each removal:

Edges added: AB 1, BC 2, CG 2, GD 1, GF 1, GH 1, AE 4. Cost 12. (After +G, D, F, H tie at 1; alphabetical picks D, then F, then H.)

(b) Kruskal. Order AB (1), DG (1), FG (1), GH (1), BC (2), CG (2), AE (4); cost 12; this MST is unique. Disjoint-sets states with union by rank and path compression. DPV does not fix a tie rule for 5.2; below uses "alphabetically earlier root points to the later one" (same rule as 5.11). State your rule on the exam.

Union-find exercise: DPV 5.11

Singletons {1}, …, {8}; union by rank, path compression; ties: lower-numbered root points to the higher. Computed by script:

Final: one tree rooted at 8 (rank 3). Children of 8: 1, 2, 4, 5, 6, 7. Node 3 hangs under 4. Ranks: rank(8)=3, rank(4)=2, rank(2)=1, rank(6)=1, others 0.

DPV 5.9: true or false (with proof or counterexample)

Graph undirected; weights not assumed distinct unless stated. Every counterexample below was checked by enumerating all spanning trees.

HW4 P2: is edge e in the MST? O(m + n)

Distinct weights, so the MST is unique. Claim: \(e = \{u, v\}\) is in the MST iff there is no u–v path that uses only edges lighter than \(w(e)\).

procedure inMST(G, w, e = {u, v})
for all x ∈ V: visited(x) = false
explore(u), but only follow edges {x, y} with w(x, y) < w(e)
if visited(v): return "e is not in the MST"
else: return "e is in the MST"

• If v is reached: that path plus \(e\) is a cycle on which \(e\) is the unique heaviest edge. By 5.9(b), \(e\) is in no MST.
• If v is not reached: let \(S\) = vertices reached from u. Every edge leaving \(S\) has weight \(\ge w(e)\) (otherwise its other end would have been reached), and \(e\) leaves \(S\). With distinct weights, \(e\) is the unique lightest edge across \((S, V - S)\), so by the cut property it is in the MST.
• Time: one DFS/BFS, each edge checked once: \(O(m + n)\).

HW4 P3: the divide-and-conquer MST algorithm is wrong

The algorithm outputs the lightest edge between \(V_1\) and \(V_2\), then recurses on each half. It can only ever output one edge across each split, and it is forced to use edges inside each half.

True MST = {AB, AC, AD}, cost 6. Every balanced split gives a wrong answer, because the star needs two edges inside no half. The algorithm is incorrect. (Checked by script.)

5 · Huffman encoding

Do: put all symbols in a min-heap by frequency; repeatedly remove the two smallest, merge them under a new node whose frequency is their sum; insert it back. \(n - 1\) merges, \(O(n \log n)\).

procedure Huffman(f)
Input: array f[1..n] of frequencies
Output: an encoding tree with n leaves
let H be a priority queue of integers, ordered by f
for i = 1 to n: insert(H, i)
for k = n + 1 to 2n − 1:
    i = deletemin(H), j = deletemin(H)
    create a node numbered k with children i, j
    f[k] = f[i] + f[j]
    insert(H, k)

Why greedy works: the two least frequent symbols can be placed as siblings at the deepest level of some optimal tree (swap them down; cost does not increase). Merging them gives a smaller instance of the same problem.

Worked: lecture example (130 million symbols)

A 70, B 3, C 20, D 37 (millions). Merges: B + C = 23; 23 + D = 60; 60 + A = 130. Depths: A 1, D 2, B 3, C 3.

Cost \(= 70\cdot1 + 37\cdot2 + 3\cdot3 + 20\cdot3 = 213\) = internal nodes \(23 + 60 + 130 = 213\) megabits, vs 260 for a fixed 2-bit code.

DPV 5.13 and 5.14 (from answers.txt)

Which child gets 0 or 1 is arbitrary; codeword lengths are what is graded.

DPV 5.15: which codes can Huffman produce?

• (a) {0, 10, 11}: possible. Example \((f_a, f_b, f_c) = (0.5, 0.3, 0.2)\): merge b, c first, then a joins at the root. Any frequencies where a is the largest work.
• (b) {0, 1, 00}: impossible. 0 is a prefix of 00, and Huffman codes are always prefix-free (symbols are leaves).
• (c) {10, 01, 00}: impossible. The tree is not full: node "1" has only one child (10). Every Huffman merge creates a node with two children. (Also, replacing 10 by 1 is strictly shorter, so this code is never optimal.)

DPV 5.16 (and HW4 P5): length-1 codewords

Setup used in both proofs. With \(n \ge 3\) symbols, just before the second-to-last merge exactly three nodes remain, \(P \le Q \le R\), with \(P + Q + R = 1\). Huffman merges \(P\) and \(Q\), then merges \(P + Q\) with \(R\). So the root's children are \(R\) and the internal node \(P + Q\). A codeword of length 1 exists iff \(R\) is a leaf. (With \(n = 2\) both codewords have length 1.)

(a) Some frequency \(f_a > 2/5\) ⇒ some codeword has length 1. Suppose \(R\) is internal, built earlier by merging \(R_1, R_2\). At that time \(R_1, R_2\) were the two smallest nodes, so every other node then present was \(\ge \max(R_1, R_2)\). \(P\) and \(Q\) are sums of such nodes, so \(P, Q \ge \max(R_1, R_2)\). Where is \(a\)?

• Under \(R_1\) (or \(R_2\)): \(f_a \le R_1 \le P \le Q\), so \(P + Q + R_1 \ge 3f_a > 6/5 > 1\). Impossible.
• Under \(P\) or \(Q\): \(f_a \le Q \le R\), so \(Q + R > 4/5\) and \(P < 1/5\). Then \(R_1, R_2 \le P < 1/5\), so \(R = R_1 + R_2 < 2/5 < f_a \le R\). Contradiction.

So \(R\) is a leaf: a codeword of length 1 exists.

HW4 P5 version (the winner gets one bit). Let the winner \(w\) have the most votes and \(f_w > 0.4\). By (a), \(R\) is a leaf. If \(R \ne w\), then \(w\) lies under \(P\) or \(Q\), so \(f_w \le Q \le R\): candidate \(R\) has at least as many votes as the winner, contradicting that \(w\) is the unique top vote-getter. So \(w\)'s codeword is 1 bit. (If two candidates tie for first, Huffman's tie-break decides which one gets the 1-bit code.) Running time: tallying \(N\) ballots is \(O(N)\); Huffman on \(n\) candidates with a heap is \(O(n \log n)\).

Careful: (a) says "some codeword has length 1", not "the character above 2/5 gets it". Frequencies 0.41, 0.49, 0.10: Huffman merges 0.10 + 0.41, so the 0.41 symbol gets 2 bits and 0.49 gets the 1-bit code.

(b) All frequencies \(< 1/3\) ⇒ no codeword of length 1. Suppose \(R\) is a leaf. Then \(P + Q = 1 - R > 2/3\). But \(P \le Q \le R < 1/3\) gives \(P + Q < 2/3\). Contradiction.

DPV 5.17: longest possible codeword

Answer: \(n - 1\). A full binary tree with \(n\) leaves has \(n - 1\) internal nodes, and a root-to-leaf path passes through distinct internal nodes, so depth \(\le n - 1\). It is reached when every merge uses the node just created, i.e. each new symbol is at least the sum of all smaller ones. Example: Fibonacci frequencies 1, 1, 2, 3, 5, 8 give lengths 5, 5, 4, 3, 2, 1 (script: a = 11110, b = 11111, c = 1110, d = 110, e = 10, f = 0). Powers of two also work: \(1/2, 1/4, \dots, 1/2^{n-1}, 1/2^{n-1}\) (DPV 5.14 is the \(n = 5\) case, longest codeword 4).

6 · Horn formulas

Do: start with everything false. While some implication has all left-side variables true and its right side false, set the right side true. Then check every pure negative clause.

set all variables to false
while there is an implication that is not satisfied:
    set the right-hand variable of the implication to true
if all pure negative clauses are satisfied: return the assignment
else: return "formula is not satisfiable"

Why correct: invariant "every variable set to true must be true in every satisfying assignment" (each was forced). So the result has the fewest true variables possible. If it breaks a negative clause, any satisfying assignment would have even more true variables and break it too. Can be implemented in linear time in the formula length.

Lecture example. \((w \wedge y \wedge z) \Rightarrow x\), \((x \wedge z) \Rightarrow w\), \(x \Rightarrow y\), \(\Rightarrow x\), \((x \wedge y) \Rightarrow w\), \((\bar w \vee \bar x \vee \bar z)\), \(\bar z\).

1. \(\Rightarrow x\): set \(x\) true.
2. \(x \Rightarrow y\): set \(y\) true.
3. \((x \wedge y) \Rightarrow w\): set \(w\) true.
4. No other implication fires (both remaining ones need \(z\)). \(z\) stays false.
5. Negative clauses: \(\bar w \vee \bar x \vee \bar z\) holds (\(z\) false); \(\bar z\) holds. Satisfiable: \(w, x, y\) true, \(z\) false.

7 · Set cover (greedy approximation)

Do: repeatedly pick the set covering the most uncovered elements. Not optimal, but within a \(\ln n\) factor.

Not optimal: \(B = \{1..6\}\), \(S_1 = \{1,2,3\}\), \(S_2 = \{4,5,6\}\), \(S_3 = \{1,2,4,5\}\). Greedy takes \(S_3\) (4 new), then \(S_1\) and \(S_2\): 3 sets. Optimum \(S_1, S_2\): 2 sets.

Claim. If \(|B| = n\) and the optimal cover uses \(k\) sets, greedy uses at most \(k \ln n\) sets.

Proof (lecture). Let \(n_t\) = number of elements still uncovered after \(t\) greedy steps; \(n_0 = n\). The \(k\) optimal sets cover the remaining \(n_t\) elements, so one of them covers at least \(n_t / k\) of them. Greedy picks a set at least that good:

8 · HW4 P4: the "fewest enemies" party greedy fails

Greedy: repeatedly invite the eligible person with the fewest enemies. Counterexample (7 friends, 12 enemy pairs):

• Enemy counts: X 2; A, B, C, D 3 each; E, F 5 each.
• Greedy invites X first (fewest enemies). That rules out A and B. Left: C, D, E, F, who are all enemies of each other, so greedy invites one more. Greedy total: 2.
• Better: {A, B, C} (no enemy pair among them). Optimum: 3.

A brute-force script confirmed the maximum is 3 and that greedy ends with 2 under every tie-break, whether "fewest enemies" counts all enemies or only enemies still eligible. Why it fails: X looks cheap, but its two enemies A and B are compatible with each other, so X blocks two invitations to gain one.

Self-check