HW3 + HW4: exam-ready solutions

Conjecture 1

Graph: \(a\to b,\ b\to a,\ a\to c\). DFS starts at \(a\); neighbors and roots in alphabetical order.

Take \(u=b\), \(v=c\). There is a path \(b\to a\to c\), and \(\text{pre}[b]=2<\text{pre}[c]=4\). But \(c\)'s parent is \(a\), so \(c\) is not a descendant of \(b\) (its interval [4,5] is not inside [2,3]). The conjecture fails.

Why it fails in general: the path from \(u\) to \(v\) can leave \(u\)'s subtree through an already-visited vertex (here \(a\)), so DFS never follows it from \(u\).

Conjecture 2

Graph: \(c\to b\to a\). Vertex \(b\) has an incoming edge (\(c\to b\)) and an outgoing edge (\(b\to a\)). Run DFS with roots in alphabetical order.

• explore(\(a\)): pre 1, no out-edges, post 2. Tree \(\{a\}\).
• \(b\) is unvisited, so it starts a new tree: pre 3. Its only out-neighbor \(a\) is already visited. post 4. Tree \(\{b\}\).
• \(c\) starts a new tree: pre 5. Its only out-neighbor \(b\) is visited. post 6. Tree \(\{c\}\).

The tree containing \(b\) is just \(\{b\}\), even though \(b\) has in- and out-edges. The conjecture fails. The trick: visit \(u\)'s out-neighbor before \(u\), and visit \(u\) before its in-neighbor.

Why plain DFS with visited marks is wrong. Standard DFS marks a vertex the first time it is reached and never enters it again. With a depth limit, the first time DFS reaches a vertex may be along a long path. Then the vertex is reached at depth 5, its neighbors are cut off, and when a short path reaches it later the visited mark blocks it.

Fix: store \(\text{best}[v]\) = the smallest depth at which \(v\) has been reached in the current search, and re-enter \(v\) whenever it is reached with a strictly smaller depth.

procedure within5(G)
for all s ∈ V:
    for all v ∈ V: best[v] = ∞
    explore5(s, 0)
    reach(s) = {v ≠ s : best[v] ≤ 5}

procedure explore5(v, d)
best[v] = d
if d = 5: return                  (no more links allowed)
for each edge (v, w) ∈ E:
    if best[w] > d + 1:            (first visit, or a shorter way in)
        explore5(w, d + 1)

Correctness. Every call follows a real walk from \(s\) of length \(d\le 5\), so every reported vertex is within 5 links. Conversely, let \(s=v_0,v_1,\dots,v_k\) be a shortest path with \(k\le5\). By induction on \(i\), \(\text{best}[v_i]\) ends at \(i\): when explore5(\(v_i\), \(i\)) runs, it either calls explore5(\(v_{i+1}\), \(i+1\)) or finds \(\text{best}[v_{i+1}]\le i+1\) already (it cannot be smaller than the true distance \(i+1\)). So every vertex within 5 links is reported.

Running time. Each call on \(w\) strictly lowers \(\text{best}[w]\), which only takes values 0..5, so each vertex is entered at most 6 times per source. Each entry scans its adjacency list: \(O(6(n+m))=O(n+m)\) per source, \(O(n(n+m))\) total.

Clean alternative to mention. BFS from each station, stopping at distance 5 (BFS reaches every vertex first by a shortest path, so visited marks are safe). Same \(O(n(n+m))\). The problem says "using DFS", so give the depth-aware DFS as the main answer.

Model. Directed graph \(G=(V,E)\): a vertex per intersection, an edge \(u\to v\) per one-way street from \(u\) to \(v\). \(G^R\) is \(G\) with every edge reversed (built in \(O(n+m)\)).

(a) Is \(G\) strongly connected?

pick any s ∈ V
run explore(G, s);   if some vertex is unvisited: return "no"
run explore(G^R, s); if some vertex is unvisited: return "no"
return "yes"

Correctness. explore(\(G\), \(s\)) visits exactly the vertices reachable from \(s\). A path \(s\leadsto v\) in \(G^R\) is a path \(v\leadsto s\) in \(G\), so explore(\(G^R\), \(s\)) visits exactly the vertices that can reach \(s\). If both cover \(V\), then for any \(u,v\): \(u\leadsto s\leadsto v\). If either misses a vertex, that vertex and \(s\) witness "no".

Time. Two explores plus building \(G^R\): \(O(n+m)\), linear. (Equivalently: run the linear SCC algorithm and check that there is one SCC.)

(b) Town hall \(s\)

Graph property: every vertex reachable from \(s\) can reach \(s\). Equivalently, the SCC containing \(s\) is a sink SCC of the metagraph (no edge leaves it).

R  = set visited by explore(G, s)      (vertices reachable from s)
R' = set visited by explore(G^R, s)    (vertices that can reach s)
if R ⊆ R': return "claim true"  else return "claim false"

Correctness. The claim says exactly: for all \(v\in R\), \(v\in R'\). Sink view: \(R\cap R'\) is the SCC of \(s\). If \(R\subseteq R'\), everything reachable from \(s\) lies in \(s\)'s SCC, so no edge leaves it (sink). If some \(v\in R\setminus R'\), then \(v\) is reachable from town hall but cannot get back, so the claim is false.

Time. Two explores and a membership check with boolean arrays: \(O(n+m)\).

Answer: the number of vertices on the longest path in the DAG. Compute \(\text{sem}(v)\) = number of vertices on the longest path ending at \(v\).

procedure semesters(G)
linearize G (DFS; vertices in decreasing post order)   (if a back edge appears: no valid schedule)
for all v ∈ V: sem(v) = 1
for each v in linearized order:
    for each edge (v, w) ∈ E:
        sem(w) = max(sem(w), sem(v) + 1)
return max over v of sem(v)

Correctness. Lower bound: courses on a path \(v_1\to\cdots\to v_k\) must be taken in strictly increasing semesters, so at least \(k\) semesters. Upper bound: take each \(v\) in semester \(\text{sem}(v)\). For each edge \(u\to v\), \(\text{sem}(v)\ge\text{sem}(u)+1\), so every prerequisite is done earlier. The last semester used is \(\max\text{sem}\). In topological order, all edges into \(w\) are processed before \(w\) pushes to its successors, so \(\text{sem}(w)\) is final when used.

Time. Linearize \(O(n+m)\), one pass over all edges \(O(n+m)\).

Worked example. Edges \(A\to C, B\to C, C\to D, B\to E, E\to D, D\to F\). Order \(A,B,C,E,D,F\) gives sem = \(A{:}1, B{:}1, C{:}2, E{:}2, D{:}3, F{:}4\). Answer 4 semesters (path \(A\to C\to D\to F\)).

Equivalent view: repeatedly take all current sources as one semester and delete them; the number of rounds is the answer (also \(O(n+m)\) with in-degree counts).

Idea. During DFS from \(r\), the current root-to-\(v\) path is on the recursion stack. Keep it in an array indexed by depth: \(\text{path}[0]=r,\dots,\text{path}[d]=v\). Then the \(k\)-th ancestor of \(v\) is \(\text{path}[d-k]\) when \(k\le d\). When \(k\ge d\), the answer is \(r\), because \(p(r)=r\) keeps you at the root.

procedure relabel(T, r)
path = array of size n
explore(r, 0)
for all v ∈ V: l(v) = lnew(v)       (write back only at the end)

procedure explore(v, d)
path[d] = v
if l(v) ≥ d: lnew(v) = l(r)
else:        lnew(v) = l(path[d − l(v)])
for each child u of v:
    explore(u, d + 1)

Correctness. When explore(\(v,d\)) runs, entries \(\text{path}[0..d]\) are exactly the vertices on the tree path from \(r\) to \(v\) (entry \(i\) was written by the ancestor at depth \(i\), and deeper entries left by earlier siblings are never read). Moving \(k\) steps up from depth \(d\) lands at depth \(d-k\), which is \(\text{path}[d-k]\). If \(k\ge d\) we hit \(r\) and stay there. New labels are stored in a separate array so every lookup uses old labels.

Time. Each vertex is visited once with \(O(1)\) work: \(O(n)\).

Worked example. Tree \(r-a-b-c\) (a chain) plus \(r-d\). Labels \(l(r)=2, l(a)=0, l(b)=1, l(c)=2, l(d)=3\).

Algorithm. Dijkstra where the key of a vertex is the earliest known arrival time, and the "length" of an edge depends on when you enter it.

procedure earliest(G, f, home, work, t0)
for all u ∈ V: arr(u) = ∞;  prev(u) = nil
arr(home) = t0
H = makequeue(V)            (keys: arr values)
while H is not empty:
    u = deletemin(H)
    for all edges (u, v) ∈ E:
        if arr(v) > arr(u) + f_uv(arr(u)):
            arr(v) = arr(u) + f_uv(arr(u));  prev(v) = u
            decreasekey(H, v)
return arr(work) − t0

Why it is correct. Two facts. (i) Travel times are \(\ge0\), so arrival times never decrease along a path. (ii) FIFO: arrival at the end of an edge is an increasing function of entry time, so arriving earlier at \(u\) is never worse, and waiting never helps. Claim: when \(u\) is removed, \(\text{arr}(u)\) is the earliest possible arrival. Suppose not, and take a truly earliest route \(P\) to \(u\). Let \((x,y)\) be the first edge of \(P\) leaving the set of removed vertices. \(x\) was removed with the correct earliest time, and \(P\) enters \((x,y)\) at some time \(\ge \text{arr}(x)\); by FIFO, entering at \(\text{arr}(x)\) gets to \(y\) no later than \(P\) does. So \(\text{arr}(y)\le\) (\(P\)'s time at \(y\)) \(\le\) (\(P\)'s time at \(u\)) \(<\text{arr}(u)\), using fact (i). Then \(y\) would have been removed before \(u\), a contradiction. This is exactly the standard Dijkstra proof with "\(\text{dist}(x)+\ell(x,y)\)" replaced by "\(\text{arr}(x)+f_{xy}(\text{arr}(x))\)".

Time. Same as Dijkstra with a binary heap: \(O((n+m)\log n)\), assuming each \(f_{ij}(t)\) is evaluated in \(O(1)\) (\(m\) evaluations total).

Graph. Vertex per currency, edge \(i\to j\) for every pair, length \(w_{ij}=-\log r_{ij}\) (a real number, possibly negative). For a path \(P\):

because \(\log\) is increasing and turns products into sums.

(a) Best conversion \(s\to t\)

for all i, j: w(i, j) = −log r_ij
for all u ∈ V: dist(u) = ∞;  prev(u) = nil
dist(s) = 0
repeat n − 1 times:
    for all edges (i, j):
        if dist(j) > dist(i) + w(i, j):
            dist(j) = dist(i) + w(i, j);  prev(j) = i
follow prev from t back to s;  best amount of t per unit of s = e^(−dist(t))

Use Bellman-Ford, not Dijkstra, since weights can be negative. This assumes no anomaly (otherwise "best" is unbounded). With no negative cycle, a shortest path has at most \(n-1\) edges, so \(n-1\) rounds suffice. \(O(nm)=O(n^3)\) since the graph is complete.

(b) Detect an anomaly

A cycle with \(\prod r>1\) is exactly a cycle with \(\sum(-\log r)<0\): a negative cycle. Run Bellman-Ford for \(n-1\) rounds, then one more round. If any dist changes in round \(n\), there is a negative cycle (anomaly); if nothing changes, there is none. Since every pair has a rate, every currency is reachable from \(s\), so one run catches any negative cycle. (If some rates were missing, add a super-source with 0-length edges to every currency, or start with all dist = 0.) Time \(O(n^3)\).

Note: \(r_{ij}r_{ji}<1\) only rules out 2-cycles; longer cycles can still be anomalies.

Assumption: a left-to-right move strictly increases \(x\) (no vertical moves). See the note at the end.

procedure monotone(G, c, s, t)
for each edge {v, w}:
    if x(v) < x(w): keep it as v → w
    if x(w) < x(v): keep it as w → v
sort V by x-coordinate                 (this is a topological order)
for all u ∈ V: dist(u) = ∞;  prev(u) = nil
dist(s) = 0
for each v ∈ V in increasing x:
    for all edges (v, w):
        if dist(w) > dist(v) + c(v, w):
            dist(w) = dist(v) + c(v, w);  prev(w) = v
return dist(t), and the path from following prev back from t

Correctness. A path is monotone exactly when it uses only the kept directed edges. Every kept edge goes from smaller \(x\) to larger \(x\), so there is no directed cycle: the graph is a DAG and increasing \(x\) is a topological order. In a DAG, processing vertices in topological order and relaxing their out-edges gives correct shortest paths even with negative costs: when \(v\) is processed, every edge into \(v\) has already been relaxed, so \(\text{dist}(v)\) is final (induction along the order). Dijkstra would be wrong here because of negative costs; Bellman-Ford works but is slower.

Time. Orienting edges \(O(m)\), sorting \(O(n\log n)\), one relaxation per edge \(O(n+m)\). Total \(O(n\log n+m)\).

Vertical moves. If equal-\(x\) moves were allowed, they could form cycles (up then down), and with prizes those could be negative cycles, so the problem would need extra rules. If they are allowed in one direction only (say upward), sort by \((x,y)\) instead; that is still a topological order and the same algorithm works.

Claim. \(e\) is in the MST \(\iff\) there is no \(u\)–\(v\) path using only edges of weight \(<w\).

procedure inMST(G, e = (u, v), w)
G' = (V, {edges of G with weight < w})
run explore(G', u)
return "yes" if v was not visited, else "no"

Proof (⇐, no lighter path ⇒ \(e\) in MST). Let \(S\) = vertices reachable from \(u\) in \(G'\). Then \(u\in S\), \(v\notin S\). Any edge crossing \((S, V-S)\) has weight \(\ge w\): a lighter crossing edge would make its outside endpoint reachable, so it would be in \(S\). Weights are distinct, so \(e\) is the unique lightest edge across this cut. By the cut property, \(e\) is in an MST; since distinct weights make the MST unique, \(e\) is in the MST.

Proof (⇒, lighter path exists ⇒ \(e\) not in MST). Let \(P\) be a \(u\)–\(v\) path of edges lighter than \(w\). Suppose the MST \(T\) contains \(e\). Removing \(e\) splits \(T\) into two parts, one with \(u\), one with \(v\). \(P\) goes from \(u\) to \(v\), so some edge \(e'\in P\) crosses between the parts. \(T-e+e'\) is a spanning tree that weighs less (\(w(e')<w\)). Contradiction. (This is the cycle property: \(e\) is the heaviest edge on the cycle \(P+e\).)

Time. Building \(G'\) is one pass over the edges, explore is \(O(n+m)\). Total \(O(n+m)\).

No. The algorithm forces the MST to contain a spanning tree of each half, but the MST may connect a half's vertices through the other half (using several crossing edges), while the algorithm uses only one crossing edge per level.

Counterexample. \(K_4\) on \(a,b,c,d\) with weights \(ab=1,\ ac=2,\ ad=3,\ bc=4,\ bd=5,\ cd=6\).

The algorithm splits 4 vertices into two pairs. Then it outputs the edge inside each pair (the 2-vertex recursions) plus one crossing edge. Two disjoint edges can never both be in a star, so every possible split fails:

Each output is a spanning tree of weight 8 or 9, but the MST weighs 6. So the algorithm is incorrect. (On the exam, one split is enough; showing it fails for all splits blocks the objection "you chose a bad split".)

Where the "proof" breaks: the first edge it outputs is correct (lightest edge across a cut, by the cut property). The recursion is the bug: the MST restricted to \(V_1\) need not be connected, so it need not be an MST of \(G_1\).

Counterexample. 7 friends \(x,a,b,c,d,e,f\). Enemy pairs: \(x\)–\(a\), \(x\)–\(b\); \(a\) and \(b\) each dislike \(d\) and \(e\); and \(c,d,e,f\) all dislike each other (a 4-clique).

• Greedy: invites \(x\) (2 enemies, strictly fewest). That rules out \(a\) and \(b\). The people left, \(c,d,e,f\), all dislike each other, so greedy can invite only one more. Total 2.
• Better party: \(\{a,b,c\}\): \(a\)–\(b\), \(a\)–\(c\), \(b\)–\(c\) are not enemy pairs. 3 guests.

So greedy invites 2 < 3 = maximum. This holds for every tie-break and whether "fewest enemies" is counted in the whole group or only among people still eligible (after \(x\) is invited the rest is a clique either way); a brute-force check confirmed maximum = 3 and greedy = 2 in all cases.

Why it fails: \(x\) has few enemies, but those enemies (\(a,b\)) are exactly the people who can coexist with others; inviting \(x\) gains 1 and blocks 2.

Setup. Let \(N\) be the number of votes and use fractions: \(f(\cdot)\) = votes / \(N\), so the weights in Huffman's priority queue always sum to 1. Each step removes the two trees of smallest weight and merges them. A leaf's codeword length = number of merges it takes part in. Let \(x\) be the winner: \(f(x)>0.4\) and \(f(x)>f(z)\) for every other candidate \(z\). If \(n=2\), both codewords have length 1, so assume \(n\ge3\).

Claim. \(x\) is untouched (still a single leaf) until the last merge. Then the last merge joins \(x\) with the tree of everyone else, so \(x\) is a child of the root: a 1-bit codeword.

Proof. Suppose instead that leaf \(x\) is merged with some tree \(y\) at a step that is not the last.

1. Not the last step means some third tree \(w\) is in the queue. \(x,y\) were the two smallest, so \(f(w)\ge f(x)>0.4\). A fourth tree would also weigh \(>0.4\), and three trees of weight \(>0.4\) exceed 1, so the queue is exactly \(\{x,y,w\}\) and \(f(y)=1-f(x)-f(w)<1-0.4-0.4=0.2\).
2. \(w\) is not a single leaf: a leaf with \(f(w)\ge f(x)\) would be a candidate with at least as many votes as the winner. So \(w\) was created earlier by merging two trees \(p,q\), and \(f(w)=f(p)+f(q)\).
3. At that earlier step the queue held \(p,q\), the leaf \(x\), and some other trees \(C\). Every merge after that step avoids \(x\) (untouched until now) and \(w\) (still in the queue now), so the trees in \(C\) merge only among themselves, ending as the single tree \(y\). Hence \(C\) is non-empty and \(f(y)=\sum_{z\in C}f(z)\).
4. \(p,q\) were the two smallest then, so each \(z\in C\) has \(f(z)\ge\max(f(p),f(q))\ge f(w)/2\). Therefore \(f(y)\ge f(w)/2>0.4/2=0.2\).

Step 4 says \(f(y)>0.2\); step 1 says \(f(y)<0.2\). Contradiction. So \(x\) is merged only at the last step and its codeword is 1 bit. \(\blacksquare\)

Both conditions matter (checked by script): votes 40, 20, 20, 20 (exactly 40%) can give the winner a 2-bit code; and a tie 41, 41, 18 can give one of the two leaders 2 bits. DPV 5.16(a) itself only says "some codeword has length 1"; the "unique winner" condition is what pins it to the winner.

Running time. Count votes: one pass over \(N\) ballots with an array indexed by candidate, \(O(N)\). Huffman with a binary heap: \(n\) inserts, \(2(n-1)\) deletemins, \(n-1\) inserts, \(O(n\log n)\). Read off the winner as the heavier leaf child of the root, \(O(1)\). Total \(O(N+n\log n)\).

Subproblem. \(r(j)\) = best net revenue for a rod of length \(j\) (\(0\le j\le n\)).

Recurrence. Decide the length \(i\) of the first piece. If \(i=j\) there is no cut. If \(i<j\) we make one cut (cost \(c\)) and then solve the remaining length \(j-i\) optimally (its own cuts are paid inside \(r(j-i)\)).

procedure rodcut(p, n, c)
r(0) = 0
for j = 1 to n:
    r(j) = p_j;  s(j) = j                (no cut)
    for i = 1 to j − 1:
        if p_i + r(j − i) − c > r(j):
            r(j) = p_i + r(j − i) − c;  s(j) = i
return r(n)
(pieces: while n > 0: output s(n); n = n − s(n))

Why \(p_n\) is a separate case. The old recurrence \(\max_{1\le i\le j}(p_i+r(j-i))\) treats "no cut" as \(i=j\). If you just subtract \(c\) inside it, the \(i=j\) term becomes \(p_j-c\), charging a cut that never happens. Example with the textbook prices \(p_1..p_8=1,5,8,9,10,17,17,20\) and \(c=2\): the correct \(r(8)=20\); the sloppy version gives 18.

Correctness. Any solution either has no cut (value \(p_j\)) or has a first piece of length \(i<j\), one cut after it, and a cutting of the remaining \(j-i\) whose net value is at most \(r(j-i)\). The recurrence tries all of these, so by induction on \(j\) it is optimal.

Time. \(n\) entries, \(O(j)\) work each: \(O(n^2)\). Space \(O(n)\).

Worked numbers (same prices, \(c=1\)): \(r(1..8)=1,5,8,9,12,17,17,21\); \(r(8)=21\) from pieces 2 + 6: \(5+17-1\).

Subproblem. \(P(j)\) = minimum total penalty of a trip from milepost 0 that ends the day at hotel \(j\). Set \(a_0=0\).

Recurrence. Look at the previous stop \(i\) (\(i=0\) means the start).

procedure hotels(a_1..a_n)
a_0 = 0;  P(0) = 0
for j = 1 to n:
    P(j) = ∞
    for i = 0 to j − 1:
        if P(i) + (300 − (a_j − a_i))² < P(j):
            P(j) = P(i) + (300 − (a_j − a_i))²;  back(j) = i
output P(n); stops: j = n; while j ≠ 0: output a_j; j = back(j)   (reverse the list)

Correctness. An optimal trip to \(j\) has some last-but-one stop \(i<j\); the trip up to \(i\) must itself be optimal (otherwise swap in a cheaper one), and the last day costs \((300-(a_j-a_i))^2\). The recurrence tries every \(i\).

Time. \(n\) entries, \(O(j)\) each: \(O(n^2)\). Space \(O(n)\).

Worked example. Hotels at 200, 350, 520, 650, 900.

Stops: 350, 650, 900, total penalty 5000 (matches brute force over all \(2^4\) stop sets).