2023 Term 2 · Forenoon — 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
Four algorithms, four different answers on one map - DFS wanders, Best First chases h, A* gets baited, and only BnB walks out with the true 120.
Q2 — TSP Branch-and-Bound
Reading a finished BnB tree backwards: the refine order falls out of a priority queue, the optimal leaf hides under an excluded edge, and the tour rebuilds by degree-forcing.
Q3 — Games: Strategy + Alpha-Beta
An unbalanced tree worth 14 at the root - the right MIN child wins, SSS* proves it with just three solved leaves, and alpha-beta's knife falls on D and E.
Q4 — AO* Problem Decomposition
The marker flees the AND-connector twice: A's expensive child stings S to 60, C undercuts at 70 - and the keyed 90 emerges once H resolves through its primitive.
Q5 — Rete Expert System
Resistor Rete net with a three-deep beta chain: how the join topology alone predicts which tuples can exist before any WME arrives.
Q6 — Planning: Applicable/Relevant/Mutex
The Blocks World four-pack: applicable now, relevant to the goal, layer-1 action mutexes, and the proposition mutexes they force next layer.
Q7 — Waltz Line Labeling
Full junction dictionary in hand: how a Y3-W1-L1-W1 chain of forced labels emerges, and the two kill-chains that turn the second drawing into NIL.