What to hand in

algo with route and frontier, passing go test ./..., plus a report. This is the last homework of the course; the coursework brief is separate.

1. The whole table

One table, your own measurements, n = 1,000 and 10,000:

	hops	days	frontier work	time
BFS (lesson 14)
Dijkstra, linear scan
Dijkstra, heap

Average over every reachable destination, not one pair.

Then state the two ratios — work and time — and say which one you would put in a report to somebody deciding whether to make the change. Justify the choice.

2. The assumption under each algorithm

Every algorithm in this course rests on a condition that, if broken, does not slow it down but makes it wrong.

Name the condition for each, in one line:

• binary search (lesson 6)
• the hash index (lesson 10)
• Dijkstra (lesson 15)
• CSA (lesson 15)

Then, for each, say what happens when it is broken: an error, a slowdown, or a confidently wrong answer. One of the four is different from the others — say which and why that makes it the most dangerous.

3. When would you build A*

Step 6 measured A* losing, and explained why: the heuristic saw 4.1% of the cost.

Describe a graph problem where a geometric heuristic would see most of the cost, and estimate what A* would prune there. Then describe one where it would see nothing at all.

Neither may be public transport or road routing — those are the two in the step.

4. The cost model is a decision

The weights were wait 2.0 and a 5-minute transfer penalty, both from the literature, and the measurement showed 149 of 200 routes taking fewer transfers with 10 arriving later.

Choose different weights for a rider you name — a parent with a pushchair, a night-shift worker, a tourist with luggage — and justify each number.

Then say what you would have to measure to find out whether your weights are better than the defaults. "It feels right" is not a measurement, and neither is "the routes look nicer".

5. The last question

One page, your own words.

You have measured a linear scan, a binary search, four sorts, two non-comparison sorts, a hash index, two trees, a heap, two graph searches and three shortest-path algorithms.

Describe a problem you have actually met — at work, in another course, in a project — and say what you would do differently now. Not which structure you would use: what you would MEASURE first, and what question you would ask before measuring.

If your answer is a structure name, read step 8 again.