// JOSH SMITHGallery

// 159.302 ARTIFICIAL INTELLIGENCE

Study guide

Each section gives the method step by step, the course conventions, a worked example taken from the tutorials or the sample exam (checked against the official answers), and the mistakes the wrong options are built from. Practise each part with the guided quiz; question numbers are given at the end of each card.

Guided quiz →
Before you start

The exam

Friday 6 November 2026, 9:30 am. Three hours, closed book, in person. Bring a scientific calculator, a pencil and an eraser; scratch paper is provided.

24 multiple-choice questions

TopicQuestionsTypical tasks
State-space search5Expansion sequences, Q contents at step n, paths, heuristics
CSP2Assignment sequences for BT, BT-FC, BT-FC-DVO; propagated domains
Games4Node values, (α, β) at a node, static evaluation counts
Fuzzy logic4Memberships, rule weights, crisp output, formulas
Neural networks5Outputs, δ values, weight updates, error measures
Propositional logic4Parenthesising, translation, CNF, resolution

That is about 7 minutes per question. Most are hand simulations, so the time goes into the working, not the reading. Options a–d are close variants built from common mistakes, and option e is "None of the choices is correct", which can be the right answer.

Answer formats used in the sample exam
  • A* expansion sequence: f-cost then state, hyphen-separated: 10S-6A-9D-8F-…-14G
  • Q contents: (4 EFDAS)(2 DAS)(10 CS), each path written backwards from its head state
  • CSP assignments: V1R-V2B-V2G, one item per attempted assignment
  • Alpha-beta: an (α, β) pair such as (5, +infinity)
Topic 2 · 2 exam questions

Constraint satisfaction

All examples below use the sample exam's checkerboard: squares 1, 2, 3 on the top row and 4, 5 beneath 1 and 2. Adjacent squares must differ. Domain of 5 = {B}; all others {R, B}.

Formulation and the constraint graph

  • Variables: the squares (or regions). Values: the colours. Domains: the allowed colours for each.
  • Constraints: one arc for each pair that must differ.
Board
12345

Arcs: 1–2, 2–3, 1–4, 2–5, 4–5

Variable 2 has the most constraints (3).

Full constraint propagation (arc consistency)

  1. Put every arc on a to-do list.
  2. For an arc X–Y, delete from X's domain any value with no different value left in Y's domain (and the same for Y).
  3. If a domain shrinks, re-check every arc touching that variable.
  4. Stop when nothing changes. An empty domain means there is no solution.
Checkerboard result

5 = {B} forces 2 = {R} and 4 = {R}. Then 1 = {B} (from 2 and 4) and 3 = {B} (from 2). Every domain ends with one value: 1B 2R 3B 4R 5B.

Arc-by-arc questions (Tutorial 9)

When the question lists the arcs in a fixed order, process them in exactly that order and report both domains after each arc. Changes carry forward. Write domains as letters with spaces (R B) and none for empty.

Practise: quiz Q21, Q22

Pure backtracking

  1. Take the variables in the fixed order and the values in the order given.
  2. Attempt a value and write it down, even if it fails at once.
  3. Check it only against variables that are already assigned. If it clashes, try the next value.
  4. If no value works, back up to the previous variable and try its next value.
Checkerboard, order 1 to 5, values R then B

1R-2R-2B-3R-4R-4B-5B-3B-1B-2R-3R-3B-4R-5B

2R clashes with 1R. 4R clashes with 1R. 5B clashes with 2B and 4B, so the search backs up to 3 (3B clashes with 2B), then to 1.

Practise: quiz Q24

Backtracking with forward checking

  1. Assign a value.
  2. Delete that value from the domain of every unassigned neighbour.
  3. If any domain becomes empty (a wipe-out), the assignment fails: restore the domains and try the next value.
  4. Values left in a domain are already consistent with earlier assignments, so no other check is needed.
AttemptForward checkOutcome
1RD2 = {B}, D4 = {B}ok
2BD3 = {R}, D5 = {} wipe-out, back up to 1
1BD2 = {R}, D4 = {R}ok
2RD3 = {B}, D5 = {B}ok
3B–ok
4RD5 = {B}ok
5B–solution
Answer format

1R-2B-1B-2R-3B-4R-5B: 7 attempts against 14 for pure backtracking. The failing 2B is still listed.

Practise: quiz Q23

Dynamic variable ordering

  • Most constrained variable: next, assign the variable with the fewest values left in its current domain.
  • Break ties by the variable involved in the most constraints with unassigned variables, then by the order given (or lowest number). State the rule you used if the question does not.
  • Least constraining value: try first the value that removes the fewest options from neighbours.
Checkerboard with BT-FC and DVO (sample exam 2.5)

5 has one value: 5B → D2 = {R}, D4 = {R}. 2 and 4 both have one value; 2 wins the tie: 2R → D1 = {B}, D3 = {B}. Then 1B, 3B, 4R.

5B-2R-1B-3B-4R: 5 attempts, no backtracking.

Tutorial 9's B.3 answer uses DVO without forward checking: it starts with D (domain {B}), then C, and needs 12 steps because nothing prunes the later domains.

Practise: quiz Q25

True or false facts (Tutorial 9)

  • Propagation alone usually solves the problem: false, search is still needed.
  • Propagation leaves every domain non-empty, so a solution exists: false. Three mutually different variables with {R, B} each pass but have no solution.
  • Propagation empties a domain, so there is no solution: true.
  • Propagation leaves every domain with one value, so there is a unique solution: true.
  • One pass over all arcs takes on the order of e·d² arc tests: true.
  • Forward checking must check the new value against all earlier assignments: false.
  • Search with full propagation uses fewer arc tests than forward checking alone: false.
  • BT-FC never explores more values than pure backtracking: true. Never tests more arcs: false.

Practise: quiz Q26

Topic 3 · 4 exam questions

Games: Minimax and alpha-beta

The example is the sample exam tree. MAX at the root, MIN below it, MAX above the leaves 6, 9 · 4, 5 · 2, 6 · 11, 3.

Minimax

  1. Work from the leaves up. Every leaf is one static evaluation.
  2. A MAX node takes the largest child value; a MIN node takes the smallest.
  3. Write in each node its return value and the number of static evaluations below it.
Sample exam 3.1

MAX level: D = 9, E = 5, F = 6, G = 11. MIN level: B = 5, C = 6. Root A = 6 with 8 static evaluations.

Alpha-beta pruning

α is the best score MAX is guaranteed so far; β is the best score MIN is guaranteed. The course uses this pseudocode:

MAX-VALUE(state, α, β, depth)
  if depth == 0: return EVAL(state)
  for each s in SUCCESSORS(state):
      α = max(α, MIN-VALUE(s, α, β, depth-1))
      if α ≥ β: return α        // cut-off
  return α

MIN-VALUE(state, α, β, depth)
  if depth == 0: return EVAL(state)
  for each s in SUCCESSORS(state):
      β = min(β, MAX-VALUE(s, α, β, depth-1))
      if β ≤ α: return β        // cut-off
  return β
The three parts of each node
  • Initial (α, β): exactly the parent's current pair at the moment it calls this child. The root starts at (−∞, +∞).
  • Return value, number of static evaluations: what the node passes up, and how many leaves were actually evaluated below it.
  • Updated (α, β): the pair when the node finishes. MAX nodes only change α; MIN nodes only change β.
A6, 7B5, 4C6, 3D9, 2E5, 2F6, 2G11, 1694526113MAXMINMAX

Next to each node: return value, static evaluations (alpha-beta, left to right). The faded leaf 3 is pruned.

NodeTypeInitial (α, β)Return, evalsUpdated (α, β)Why
DMAX(−∞, +∞)9, 2(9, +∞)max(6, 9)
EMAX(−∞, 9)5, 2(5, 9)B passed down β = 9; 4 then 5, no cut
BMIN(−∞, +∞)5, 4(−∞, 5)min(9, 5)
FMAX(5, +∞)6, 2(6, +∞)A passed α = 5 to C, C to F; 2 leaves α at 5, then 6
GMAX(5, 6)11, 1(11, 6)11 ≥ 6: cut, leaf 3 is never evaluated
CMIN(5, +∞)6, 3(5, 6)min(6, 11)
AMAX(−∞, +∞)6, 7(6, +∞)max(5, 6); 7 of 8 leaves evaluated
Common mistakes
  • Giving a child its parent's initial pair instead of its current one. C gets (5, +∞), not (−∞, +∞).
  • Expecting the return value to be "sensible" at a cut node. G returns 11, which is bigger than β; that is correct for this pseudocode.
  • Counting pruned leaves in the static evaluation count.
  • Changing α at a MIN node or β at a MAX node.

Tutorial 11's answer key follows the same rules: its root records 8 with 7 static evaluations.

Practise: quiz Q27–Q30, Q32–Q34

Visiting order and pruning

  • "Right to left" means the same algorithm with every node's children taken in reverse order. Redraw the tree mirrored if that helps.
  • Pruning never changes the root value, only the number of static evaluations.
  • Best case: when the strongest move is searched first at every node, alpha-beta evaluates roughly bd/2 leaves instead of bd. Worst case: no pruning at all.
  • A cut can happen after the last child, in which case nothing is saved.

Practise: quiz Q31, Q35

Topic 4 · 4 exam questions

Fuzzy logic

The worked example is Tutorial 7 itself: x = −0.7, y = −3.

The pipeline

  1. Fuzzify: find each input's degree of membership in every fuzzy set.
  2. Fire the rules: each FAMM cell is a rule; its weight is the Zadeh AND (minimum) of its two memberships.
  3. Defuzzify: centre of mass of the rule outputs, weighted by the rule weights.

Membership functions

abcd10(x − a)/(b − a)(x − d)/(c − d)1
Ftrapezoid(x)=max⁡ ⁣(min⁡ ⁣(x−ab−a, 1, x−dc−d), 0)F_{\text{trapezoid}}(x) = \max\!\left(\min\!\left(\frac{x-a}{b-a},\ 1,\ \frac{x-d}{c-d}\right),\ 0\right)
Fleft(x)=max⁡ ⁣(min⁡ ⁣(1, x−dc−d), 0)Fright(x)=max⁡ ⁣(min⁡ ⁣(1, x−ab−a), 0)F_{\text{left}}(x) = \max\!\left(\min\!\left(1,\ \frac{x-d}{c-d}\right),\ 0\right) \qquad F_{\text{right}}(x) = \max\!\left(\min\!\left(1,\ \frac{x-a}{b-a}\right),\ 0\right)

Where the leg formulas come from (Week 5)

The rising leg is the line through (a, 0) and (b, 1): slope 1/(b − a), so y = (x − a)/(b − a). The falling leg goes through (c, 1) and (d, 0): slope 1/(c − d), so y = (x − d)/(c − d). Check each at its endpoints: 0 at a, 1 at b; 1 at c, 0 at d.

Reading the course tables

In the Tutorial 7 table, the left shoulder NEG lists a = b = 0 and only c, d matter; the right shoulder POS lists c = d = 0 and only a, b matter. The zeros are placeholders, not breakpoints.

InputSetFormulaValue
x = −0.7NEG (c −1, d −0.57)(−0.7 + 0.57)/(−1 + 0.57)0.30
x = −0.7ZE (a −1, b −0.57)(−0.7 + 1)/(−0.57 + 1)0.70
x = −0.7POS (a 0.57)below a0
y = −3S (c −4, d −2)(−3 + 2)/(−4 + 2)0.50
y = −3M (a −4, b −2)(−3 + 4)/(−2 + 4)0.50
y = −3L (a 2)below a0

Practise: quiz Q36–Q39

Rules and the FAMM

y \ xNZEP
SNL (W1)NS (W4)NS (W7)
MNS (W2)ZE (W5)PS (W8)
LPS (W3)PS (W6)PL (W9)
  • Rules are numbered down each column: W1–W3 under x = N, W4–W6 under ZE, W7–W9 under P.
  • Rule 2 reads: IF x is N AND y is M THEN output is NS.
  • Weight = min(μx, μy). Max would be Zadeh OR; product is a different AND.

Tutorial 7: W1 = min(0.30, 0.50) = 0.30, W2 = 0.30, W4 = min(0.70, 0.50) = 0.50, W5 = 0.50. Every other weight is 0 because one of its memberships is 0.

Practise: quiz Q40

Defuzzification: centre of mass

crisp=∑i=19Wi⋅outputi∑i=19Wi\text{crisp} = \frac{\sum_{i=1}^{9} W_i \cdot \text{output}_i}{\sum_{i=1}^{9} W_i}

When asked to "write the complete formula", write all nine terms with their linguistic outputs:

(W1·NL + W2·NS + W3·PS + W4·NS + W5·ZE + W6·PS + W7·NS + W8·PS + W9·PL) / (W1 + W2 + … + W9)

Common mistakes
  • Dividing by 9 (the number of rules) or by the number of fired rules instead of the sum of the weights.
  • Reading the weights across the rows instead of down the columns.
  • Averaging the fired outputs without weighting them.

Practise: quiz Q41, Q43

Full example: Tutorial 7

RuleWeightOutputW × output
W1 (N, S)0.30NL = −5−1.50
W2 (N, M)0.30NS = −2.5−0.75
W4 (ZE, S)0.50NS = −2.5−1.25
W5 (ZE, M)0.50ZE = 00
Sum1.60−3.50
Crisp output

−3.50 / 1.60 = −2.19

Practise: quiz Q42

Topic 5 · 5 exam questions

Neural networks: backpropagation

The worked example is Tutorial 8a: inputs x = 1, y = 0, target z = 1, every weight 0.1, η = 2, sigmoid everywhere, a bias input of 1 into both h and z, and x and y also wired straight to z.

Forward pass

netj=∑iWij OiOj=11+e−netjnet_j = \sum_i W_{ij}\,O_i \qquad O_j = \frac{1}{1+e^{-net_j}}
  1. Hidden node: neth = 1(0.1) + 0(0.1) + 1(0.1) [bias] = 0.2000, so Oh = 0.5498.
  2. Output node: netz = 1(0.1) + 0(0.1) + 0.5498(0.1) + 1(0.1) [bias] = 0.2550, so Oz = 0.5634.
Rounding rule from the tutorial answers

Round each intermediate result to 4 decimal places and carry the rounded value forward. Give final weights to the precision the options use (often 2 decimals).

Calculator check

sig(0) = 0.5 and sig(0.2) = 0.5498. If you get anything else, check you typed e−0.2, not e0.2.

Practise: quiz Q44, Q50

Output layer: δ and weight updates

δk=(tk−Ok) Ok (1−Ok)Wjk←Wjk+η δk Oj\delta_k = (t_k - O_k)\,O_k\,(1 - O_k) \qquad W_{jk} \leftarrow W_{jk} + \eta\,\delta_k\,O_j
  1. δz = (1 − 0.5634)(0.5634)(0.4366) = 0.1074.
  2. Wbz = 0.1 + 2(0.1074)(1) = 0.3148 → 0.31 (bias input is always 1).
  3. Wxz = 0.1 + 2(0.1074)(1) = 0.31; Wyz = 0.1 + 2(0.1074)(0) = 0.10 (y = 0, no change).
  4. Whz = 0.1 + 2(0.1074)(0.5498) = 0.2181 → 0.22.
Common mistakes
  • Using t − O without the O(1 − O) factor, or O − t (wrong sign).
  • Multiplying by the output of the receiving node instead of the sending node.
  • Leaving out η.

Practise: quiz Q45, Q46, Q51

Hidden layer: δ and weight updates

δj=Oj (1−Oj)∑kδk WjkWij←Wij+η δj Oi\delta_j = O_j\,(1 - O_j)\sum_k \delta_k\,W_{jk} \qquad W_{ij} \leftarrow W_{ij} + \eta\,\delta_j\,O_i
Course convention: use the updated Wjk

Tutorial 8a computes δh with Whz = 0.2181, the value just updated. The sample exam does the same ("the weights Wj1k1… have been updated already"). With old weights you can even get the wrong sign.

  1. δh = 0.5498(1 − 0.5498)(0.1074)(0.2181) = 0.0058.
  2. Wbh = 0.1 + 2(0.0058)(1) = 0.1116 → 0.11.
  3. Wxh = 0.1 + 2(0.0058)(1) = 0.11; Wyh = 0.10 (y = 0).

With more than one output node, sum δk Wjk over every output the hidden node feeds (Tutorial 8b).

Practise: quiz Q47, Q48, Q52

Bias nodes and direct links

  • A bias is just another input whose output is always 1. Its weight updates by η·δ every time.
  • A link from an input that is 0 never changes on that pattern.
  • In Tutorial 8a's layout, the inputs feed the output node directly as well as through h, so netz has four terms. Count the arrows into each node before you start.
  • "No bias nodes are used" (Tutorial 8b, sample exam) means leave the bias term out entirely.

Error measures

SSE=12∑p∑k(Tk−Ok)2RMSE=∑p∑k(Tk−Ok)2P⋅KSSE = \tfrac{1}{2}\sum_p\sum_k (T_k - O_k)^2 \qquad RMSE = \sqrt{\frac{\sum_p\sum_k (T_k - O_k)^2}{P \cdot K}}
  1. For each pattern table, fill in the (Tk − Ok)² row.
  2. Add every square over all patterns and all output nodes.
  3. SSE: halve the total. The sample answer (SSE = 0.27 from a total of 0.54) shows the course includes the ½.
  4. RMSE: divide the total by the number of patterns × outputs (here 3 × 3 = 9) and take the square root: √(0.54/9) = 0.24.
Check your lecture slides

RMSE definitions vary between textbooks. If the slides use a different divisor, use theirs; the method is the same.

Practise: quiz Q49, Q53

Topic 6 · 4 exam questions

Propositional logic

Course notation: ~ not, ^ and, v or, -> implies, <-> if and only if. Variables are upper case; true and false are written in lower case.

Precedence and full parenthesising

Tightest first: ~, then ^, then v, then ->, then <->. Group the tightest connectives first and keep the variables in their original order.

Tutorial expressionFully parenthesised
P v ~ Q -> R((P v ~Q) -> R)
P ^ Q v R((P ^ Q) v R)
P -> Q <-> R -> S((P -> Q) <-> (R -> S))
~ R v S -> Q ^ R((~R v S) -> (Q ^ R))

Practise: quiz Q54

Translating English

  • "If A then B": A -> B. The condition goes on the left.
  • "A only if B": also A -> B. Watch for this reversal.
  • "not" applies only to the clause it is in: "the sun does not shine" is ~S.
Tutorial sentenceLogic
If we do not go to the zoo then we stay at home.~Z -> H
If we do not stay at home then the sun shines.~H -> S
If the sun shines or we do not stay at home then we go to the zoo.(S v ~H) -> Z
If the sun does not shine then we do not go to the zoo.~S -> ~Z

Practise: quiz Q55

Simplification

RuleResultExample
P v truetrue(P ^ Q) v true = true
P ^ truePP ^ (Q v true) = P
P v falsePP ^ (Q v false) = P ^ Q
P ^ falsefalse(P ^ false) v Q = Q

Practise: quiz Q58

Conjunctive normal form

  1. Remove <->: A <-> B becomes (A -> B) ^ (B -> A).
  2. Remove ->: A -> B becomes ~A v B.
  3. Push ~ inwards with De Morgan: ~(A ^ B) = ~A v ~B, ~(A v B) = ~A ^ ~B, ~~A = A.
  4. Distribute v over ^: (A ^ B) v C = (A v C) ^ (B v C).
  5. Write the result as bracketed disjunctions joined by ^.
Tutorial 10 sentenceCNF
(A ^ ~B) -> C(~A v B v C)
(A -> B) -> C(A v C) ^ (~B v C)
A -> (B -> C)(~A v ~B v C)
((A ^ B) v C) -> D(~A v ~B v D) ^ (~C v D)
((A ^ B) v C) -> (D ^ E)(~A v ~B v D) ^ (~A v ~B v E) ^ (~C v D) ^ (~C v E)
Worked: (A -> B) -> C

~(~A v B) v C → (A ^ ~B) v C → (A v C) ^ (~B v C).

Practise: quiz Q56, Q57

Resolution refutation

  1. Convert every axiom to clauses (CNF) and number them.
  2. Add the negation of what you want to prove.
  3. Resolve two clauses that contain a complementary pair (P and ~P): the result is everything else from both clauses. Remove exactly one pair per step.
  4. Number each new clause and note its parents.
  5. When you derive the empty clause, the goal is proved.

Worked: Tutorial 10, prove ~P

#ClauseFrom
1~P v Q v Saxiom
2~Saxiom
3~Q v Xaxiom
4~Xaxiom
5Pnegated goal
6Q v S1, 5
7Q6, 2
8X7, 3
9empty clause8, 4
Common mistakes
  • Adding the goal instead of its negation.
  • Cancelling two pairs at once: (~P v Q) with (P v ~Q) gives Q v ~Q, a useless tautology, not the empty clause.
  • Getting the sign wrong: ~R with ~P v R leaves ~P.

Theorem proving: Adams, Brown and Clark

Make each suspect's statements conditional on their innocence (A = Adams is innocent, and so on), add the general knowledge rules, and encode "exactly one is guilty" as A v B, A v C, B v C. Then test each suspect: assuming Brown innocent gives ~X and ~Y, which forces ~A and ~C, contradicting A v C. So Brown is guilty.

Practise: quiz Q59–Q61

On the day

Checklist before you choose an option

  • Search: Which list (none, visited, expanded)? Where do new paths go? What breaks ties? Is the goal tested on removal? Did you include G and every dead end?
  • CSP: Fixed or dynamic order? Did you list failed attempts? With FC, did you check every unassigned neighbour for a wipe-out?
  • Games: Is each child's initial (α, β) the parent's current pair? Left to right or right to left? Did you count only evaluated leaves?
  • Fuzzy: Which trapezoid type is each set? Min for AND? Rules numbered down the columns? Divided by the sum of the weights?
  • Neural nets: 4 decimal places at each step? Sigmoid at every node? Updated Wjk for the hidden δ? η included? Bias input 1?
  • Logic: Negated the goal? One complementary pair per resolution? De Morgan flipped every sign?
  • If your answer is not listed, recheck once, then choose "None of the choices is correct".