A First Taste of Algorithms

Problem Set 5

✦ ✦ ✦

Lab 5 (Dots and Lines) is the Computational Lab tier. Problems 2.3 and 3.3 expect its code as equipment.

Fluency

1.1 Draw the Königsberg graph from the description (four land masses A, B, C, D; you may invent which bridges join which, keeping seven total and every vertex odd). Label each vertex’s degree — its count of edge-ends.

1.2 Write the hallways school as a drawing, then write this drawing back as a dictionary: vertices P, Q, R, S, T; edges PQ, PR, QR, QS, RS, ST. (Round trips between picture and dictionary should feel free by the end.)

1.3 Run BFS by hand from P on the graph of 1.2: list the rings (ring 0, ring 1, …) and give each vertex its hop-distance. Then rerun from T and watch the rings reorganize.

1.4 Run DFS by hand from P on the same graph, exploring neighbors in alphabetical order; write the sequence of visits and, separately, the moments of backing up. Compare its visit order with BFS’s.

1.5 Execute Dijkstra’s protocol on the chapter’s town map starting from School (not Home): full table of tags, with each overwrite shown struck through. Check your finished tags give the Home distance as 7.

1.6 In the town map, the city closes the School–Library path (construction). Re-run Dijkstra from Home. Which destinations got more expensive, and by how much?

Practice

2.1 Euler’s parity argument, yours. Prove: in any walk that crosses every edge exactly once, every vertex except possibly the first and last must have even degree. Scaffold: count each intermediate visit’s consumption of edge-ends (arrive + depart = ?). Conclude Königsberg’s stroll is impossible. Then the modern victory lap: the city (now Kaliningrad) lost two bridges to war and history — with the right two gone, does a walk exist? Choose which two to delete from your 1.1 drawing and exhibit the walk.

2.2 Word ladders: CAT → COT → DOG-style puzzles, one letter changing at a time, every rung a real word. Recast as a graph problem: what are the vertices, what are the edges, and what does BFS from CAT guarantee about the ladder it finds to DOG? Find by hand a shortest CAT→DOG ladder (there is one of length 3 — three edges).

2.3 “Six degrees of separation” claims any two people are ≤ 6 friendship-hops apart. Say precisely what BFS from you, on the friendship graph of Earth, would compute, ring by ring. If each person had exactly 30 new acquaintances per ring, how many people would ring 6 contain? Compare with Earth’s population, and state what that arithmetic does and does not prove about the claim. (Chapter 3’s exponential, now working for the rumor.)

2.4 Your town’s subway charges per transfer, not per stop: riding any single line any distance is one token. Model “fewest tokens from station X to station Y” as a shortest-path problem — the trick is choosing what the vertices and edges are (hint: lines, not just stations, may deserve to be vertices). Set it up; don’t solve.

2.5 A knight stands on a chessboard corner. “Fewest knight-moves to the opposite corner” is a BFS problem: say what the graph is (vertices? edges? how many of each?) and run the first three rings by hand from the corner. (Lab Break-it 4 lets the machine finish; predict the full answer now and write it down.)

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