Week 2 Tutorial: Catch an early stop
Trace a wrong implementation, complete the search core, and test the four cases that catch it.
3 March 2027
Open Week 2 in the Lab →Try your own change on this week's case.
Two-hour tutorial: preparation, coding and checks
This week’s task#
Model: The symbolic S→G=10, S→A=1, A→G=1 example first; then the kitchen→#03 graph. No energy or reservations.
Before you start · 15 minutes#
Read W2. Predict OPEN after removing S and A; write the answer an early-stop implementation returns.
Trace the example · 25 minutes#
Try stopping at discovery, then restore the starting example. Step through the search table and identify when the better goal cost appears.
Implement and compare · 55 minutes#
Complete mySearch in the practice pack. Keep best costs, parent pointers and a priority queue; stop on the non-stale goal pop. Run the provided early-discovery test.
Use Open full Lab for editable inputs, strategy code, exports and the practice pack. The example on this page compares this week’s published cases; your local student runner must call the functions you complete.
Check and explain · 25 minutes#
Add source=goal, unreachable, repeated-improvement and equal-cost tests. Report the returned path and cost; explain why discovery is too early.
What to keep: A1: Dijkstra implementation and its counterexample. Show the tutor your prediction, experiment and explanation for this week’s participation point; keep the record to develop your assignment.
Optional extension#
Switch to the canonical graph and trace one improved parent. Heuristic design is next week.
W2 · Stop when the goal is popped.
Is discovering the goal enough, or must its best entry be popped?
S is the start and G is the destination. The numbers on the arrows are travel costs. Find the cheapest route.
Returned S → A → G with cost 2. Dijkstra with goal-on-pop returns 2. The costs agree for this input.
Computed from this case · 1.73 ms · lab-1.0 · discovery
Arrows are directed edges; numbers are costs. Follow the OPEN trace to see which edge improves each distance. The graph redraws from this run's edge table.
OPEN: what remains to be searched
| Step | Node | g | f | OPEN | CLOSED |
|---|---|---|---|---|---|
| 1 | S | 0 | 0 | A, G | S |
| 2 | A | 1 | 1 | G, G | S, A |
| 3 | G | 2 | 2 | G | S, A |
Read each row after its node is popped. Finding G in OPEN is not a proof of its final cost.
Explore the evidence, replay or open full Lab
Open full Lab ↗ for editable inputs, strategy code and saved comparisons.
Compare returned cost 10 with 2. The first discovered goal is not the cheapest route.
Read the example above
Compare returned cost 10 with 2. The first discovered goal is not the cheapest route.
Symbolic teaching case · Published example units; not flight-model totals · The search frontier and relaxation
| Inspect | Step | Node | g | f | OPEN | CLOSED |
|---|---|---|---|---|---|---|
| 1 | S | 0 | 0 | A, G | S | |
| 2 | A | 1 | 1 | G, G | S, A | |
| 3 | G | 2 | 2 | G | S, A |
Continue in the Lab →The same case, with every input open to change.
The spec
What you bring to the session. Written so a reader can tell whether it has been met without asking you.
- you can predict the settle order on a new small graph before running it
- you can build a counterexample that exposes settle-on-discovery
- you can build a counterexample that exposes stop-when-goal-generated
Teaching team
- Kofi Marchetti — tutor