Five tasks. The last set in the course.

---

1. Bidirectional search

A* failed because its heuristic was blind. Here is a way to prune that needs no heuristic at all: run two searches, one forward from the origin and one backward from the destination, and stop when they meet.

Implement it. Then answer the part that catches people out: when they meet is not where the answer is. Meeting means a path exists through that node; it does not mean it is the cheapest. What extra condition makes the answer correct?

Measure settled nodes and time against plain Dijkstra on your network, over every destination. Report the ratio — and say honestly whether it was worth the extra code.

---

2. Decrease-key, and what it costs

Step 2 chose lazy deletion and measured 1.12 pushes per settled node. Build the other version.

Add a pos []int to NodeHeap recording where each node sits, keep it correct through every swap, and implement DecreaseKey.

Then measure three things: frontier work, time, and the number of heap entries. The entry count should drop to exactly 1.00 per node.

Does the time drop too? Explain the result using lesson 13's own numbers — how many swaps a build performs, and what you just added to each one.

---

3. Where the two frontiers cross

Step 5 measured a 72.7× work ratio on a graph with mean degree 1.49.

Raise the edge count and repeat. At what density does the linear scan stop losing badly? Does it ever win?

Explain with the two costs from step 2: O((V + E) log V) against O(V² + E). Find the density where they meet on paper, then check whether your measurement agrees. If it does not, say which effect the formulas leave out — you measured it in step 5.

---

4. The question CSA cannot answer

Step 7 showed CSA returning 11 transfers where Dijkstra returned 6, at the same arrival time.

Write down three real requirements a journey planner might have. For each, say whether CSA can serve it, and if not, what it would take.

• "get me there as early as possible"
• "I have a suitcase — no more than one change"
• "I will pay 10 minutes to avoid a transfer"

Then answer the design question: transit keeps all five algorithms. Would you? What would you do instead, and what would it cost you?

---

5. Your own 76×

CSA won by changing the question, not the algorithm.

Take one operation in your own algo — any of them — and find a restriction that makes it dramatically cheaper. Not a faster implementation: a narrower question.

Some places to look: algo top when k is fixed for the life of the program; algo find when the library never changes after loading; algo route when only one origin is ever asked about.

Implement it, measure both, and state precisely what you gave up. If you cannot name what you gave up, you have not found a narrower question — you have found a bug.