2023 Term 2 · 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
Search algorithms on a grid map
Q2 — TSP Branch-and-Bound
TSP BnB tree reading
Q3 — Games: Strategy + Alpha-Beta
One tree, three algorithms: strategies need one move per MAX node, alpha-beta prunes what cannot change the answer, SSS* proves it by solving nodes.
Q4 — AO* Problem Decomposition
AO* marks the AND-connector, C's expansion stings it upward, and A's primitive pair settles S - first three expansions and all three values reproduce the key exactly.
Q5 — Rete Expert System
Resistor-classification Rete net: how to file WMEs, run the itemNo joins, build the conflict set, then let specificity and recency argue.
Q6 — Planning: Applicable/Relevant/Mutex
Blocks World planning graph: the four tests - applicable now, relevant to goal, action mutexes in layer 1, proposition mutexes after.
Q7 — Waltz Line Labeling
Waltz labelling as CSP: junction dictionary, arc-consistency propagation, why some drawings settle on Y1-W1-L5-T4 and others die to NIL.