2023 Term 3 · Afternoon — Worked Solutions
Every question solved from scratch: the reasoning, the algorithm trace, and the shortcuts that get you to the answer fast.
Q1 — Search: BFS/A*/BnB
Three algorithms split three ways on one map - and the fact that A* loses to Branch-and-Bound is itself the proof that h overestimates.
Q2 — TSP Branch-and-Bound
A six-city BnB tree: the priority queue dictates b1,c1,d2,c2, a forced tour pops out at e1=432, and degree bookkeeping rebuilds A,B,C,E,F,D.
Q3 — Games: Strategy + Alpha-Beta
Three MIN children at the root: alpha-beta with running bounds kills C,E,F,I, and SSS* dismisses exactly the same five without a glance.
Q4 — AO* Problem Decomposition
A shared primitive G ties A and D together: every A-revision drags S down to 13, and only solving D's pair lets S climb to its true 18.
Q5 — Rete Expert System
Nine mushroom WMEs meet an edible/poisonous net: three tuples survive the joins, and timestamp 209 hands recency to R2.
Q6 — Planning: Applicable/Relevant/Mutex
Two towers, one empty arm: exactly two Unstacks fire now, three writers serve the goal, and the twin Unstacks are mutex because they strangle the same arm.
Q7 — Waltz Line Labeling
A hexagonal prism silhouette: junction labels chain around the outline Y-W-L-W-Y-W, and the full keyed sequence reads off as three per-drawing runs.