A First Taste of Algorithms · Problem Set 5

Concept & Counterexample

3.1 Claim: “DFS, like BFS, finds shortest paths — it explores systematically, after all.” Build the smallest maze or graph where DFS from S (neighbors explored in alphabetical order) reaches T by a path strictly longer than the shortest, and state in one sentence what the thread does that the ripple never does.

3.2 Claim: “BFS handles weighted graphs: just treat the weights as distances.” Three vertices suffice for the refutation — exhibit weights where the fewest-hops route is not the cheapest route, and say which ring BFS puts the destination in versus what Dijkstra’s tags say.

3.3 Claim: “Dijkstra works fine with a few negative weights as long as the total stays positive.” Build the three-vertex counterexample the chapter promised: Home→B direct weight 2, Home→C weight 3, C→B weight −2. Trace the protocol — at what moment does it settle a lie? Point to the sentence in the deep-water proof that your example kills, quoting its load-bearing clause.

3.4 Claim: “adding an edge to a graph never makes any shortest path longer.” True or false for nonnegative weights? Prove or refute. Then the sneaky cousin: “adding an edge never makes any DFS route longer.” (Careful: what does DFS’s route even depend on?)

3.5 Claim: “if a graph is connected, BFS from any vertex visits all vertices; therefore, to check connectivity, you must run BFS from every vertex.” Keep the first half, demolish the second: how many BFS runs does connectivity-checking actually need, and why?

Diamond

4.1 The rings are the distances. Prove: when BFS runs from vertex s, every vertex v it visits is assigned to ring d(v), where d(v) is the true minimum number of edges from s to v — and vertices never visited have no path from s at all. Structure it as induction on rings: (a) Floor: ring 0. (b) Step, two halves that students always conflate, so keep them apart: (i) everything BFS puts in ring k + 1 truly has distance ≤ k + 1 (exhibit the path — where does it come from?); (ii) nothing of true distance k + 1 gets missed or placed later (its neighbor on a shortest path lives in ring k by hypothesis — finish the sentence, and find the precise line of the queue’s discipline that this half leans on). (c) The absence clause: prove the never-visited claim by contradiction, walking a hypothetical path from s and locating its first never-visited vertex. (d) One sentence: which half of (b) fails for DFS, and which for BFS-with-weights? (Your counterexamples from 3.1 and 3.2 are the witnesses; the proof tells you where they strike.)

Computational Lab

5.1 Lab 5 in full, predictions before runs. Your hand-run of Dijkstra (Fluency 1.5) must be checked against the machine’s tags before you trust either.

Teach It

6.1 Tell someone the Königsberg story with a napkin: draw the city, then perform Euler’s deletion — redraw as four dots and seven lines while they watch — and let them hunt for the walk before you show the parity argument. Three sentences: did the abstraction step or the parity step impress them more, and why do you think that is?

6.2 Run the Dijkstra coin protocol with someone on a map of your actual neighborhood (six or seven places, walking-minutes as weights, estimated honestly). Let them be the bureaucrat — they move the coins, you only enforce the two rules. Report the first moment a detour beat a direct edge on your streets, and whether they trusted it.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses