Drills
Five tasks.
1. Make the two DFS versions agree
Step 6 showed the iterative and recursive DFS returning different paths to 552 of 554 destinations, because one walks a node's neighbours backwards.
Fix the iterative one without touching the recursive one: push the neighbours in reverse order so the stack pops them in the original order.
reversed-push DFS vs recursive: agree 554, differ 0
All 554. Explain why reversing the push order is exactly the right amount of change — and why it does not make DFS find shorter paths. (Measure: are the hop counts any better?)
Then answer the harder question: TestTheTwoDFSVersionsDisagreeOnPaths will now
fail. Should it be deleted, or should the reversed version live beside the
original? Justify it in terms of what the test was protecting.
2. Break BFS in the subtle way
Step 3 said BFS must mark a node as seen when it is put into the queue, not when it is taken out. Do it the wrong way on purpose.
mark-on-pop BFS: 230 of 554 destinations wrong, worst overshoot 3 hops
It still finds every destination. It is wrong on 41.5% of them, and never by more than 3 hops.
That combination is the point: no crash, no missing answer, no obviously silly output — just paths that are quietly a little too long. Explain the mechanism (what does the queue contain that it should not?), and say what it would take to notice this in production if there were no test.
Then measure one more thing: how much larger does the queue get?
3. BFS on the matrix
Step 7 measured memory and a full scan. Now measure the search itself.
Write a BFS that uses AdjMatrix instead of the adjacency list — for each node
it has to check all V cells to find the neighbours.
Compare at n = 1,000 / 10,000: edges looked at, and time. Confirm from your own
numbers that one is O(V + E) and the other O(V²).
Then answer: the two searches return identical paths. What exactly did the representation change, and what did it not?
4. The diameter of the library
The diameter is the longest of all the shortest paths — the two books furthest apart in borrowing terms.
Compute it by running BFS from every node. What does it cost in terms of V and
E?
Then look up the "double sweep" heuristic: BFS from any node to find the farthest
node a, then BFS from a. Compare its answer with the true diameter on your
graph, and its cost.
Does it get the right answer? Does it always? Say what you actually checked, and do not claim more than that.
5. What a layer means
BFS visits in layers. That fact answers more questions than "how many hops".
Use the layers to detect whether your graph has an odd-length cycle: while BFS runs, colour each node by the parity of its layer. If an edge ever joins two nodes of the same colour, there is one.
Implement it, run it on the library network, and report the answer.
Then say which of these three a plain DFS could also answer, and which it could not: "is it reachable", "how many hops away", "is there an odd cycle".