Recitation problems, worked

Not "solve the puzzle". You are being asked to produce the input that a generic search algorithm consumes. BFS, DFS, UCS and A* all expect exactly five things and nothing else:

• a set of states (implicitly, via a representation),
• an initial state,
• a successor function: state $\to$ (action, next state, cost) triples,
• a goal test: state $\to$ true/false,
• a cost per action (here: 1 per move, so path cost = number of moves).

The grading pressure sits in two places. First, your representation must capture everything that affects the future and nothing else — too little and the successor function is undefined, too much and your state count is wrong. Second, part (b) is a counting argument, and "it's exponential" earns nothing; you need the exact expression and a reason.

What does a move depend on? Only which disks are on which peg. Nothing in the rules refers to how you got here, whose turn it is, or how long you have been playing. So a state is exactly a distribution of the $n$ disks across the 3 pegs.

A clean encoding: three ordered lists, one per peg, each listing the disks on that peg from top to bottom.

state = (peg1, peg2, peg3)   e.g. for $n = 3$:   ([1], [3], [2])

That reads: disk 1 alone on peg 1, disk 3 alone on peg 2, disk 2 alone on peg 3.

An equivalent and slightly tidier representation: a vector $(p_1, p_2, \dots, p_n)$ where $p_i \in \{1,2,3\}$ is the peg holding disk $i$. The two representations are in bijection; the second is what makes part (b) a one-liner.

Using the vector form: each of the $n$ disks independently sits on one of 3 pegs, and every such choice gives a legal state, because the stacking order is forced.

$|S| = \underbrace{3 \times 3 \times \cdots \times 3}_{n \text{ disks}} = 3^n$

Two things worth saying out loud in an exam answer, because they are where the marks are:

• Why no factor for ordering. If order within a peg were free, a peg holding $k$ disks would admit $k!$ arrangements and the count would blow up. The constraint kills all but one, so the ordering contributes a factor of 1.
• Why no illegal states to subtract. Every disk-to-peg assignment is realisable, so $3^n$ is not an over-count that needs trimming.

Check at $n=2$. $3^2 = 9$. Enumerate them, writing each state as peg1 | peg2 | peg3:

Nine, and notice that no state like 12 | – | – has a sibling with disk 1 under disk 2 — that configuration is simply not a state.

Start. Everything on peg 1, in forced order:

start = ([1, 2, ..., n], [], [])

Goal test. Everything on peg 3:

goalTest(s) = (s == ([], [], [1, 2, ..., n]))

In the vector form both are one-liners: start is $p_i = 1$ for all $i$; the goal test is $p_i = 3$ for all $i$.

An action is "move the top disk of peg $i$ onto peg $j$", written $(i \to j)$. In the list representation: pop the front of list $i$ and push it onto the front of list $j$. It is legal when all three conditions hold:

1. $i \neq j$;
2. list $i$ is non-empty (there is something to move);
3. list $j$ is empty, or the front of list $j$ is larger than the disk being moved.

Cost 1 per action, so path cost counts moves.

How many actions are available? There are $3 \times 2 = 6$ ordered peg pairs, but almost all are blocked. Computing the branching factor over every reachable state for $n = 3$ and $n = 4$ gives the same answer both times: at least 2 and at most 3 legal moves from any state. The reasoning: the three exposed disks (one per non-empty peg) have a unique smallest, and that disk can go on either of the other two pegs — so you always have $\ge 2$ moves; and only when all three pegs are non-empty does the middle-sized exposed disk add a third.

So Hanoi is a small-branching, deep search problem: $b \le 3$, and the shallowest goal sits at depth $2^n - 1$ (7 moves for $n=3$, 15 for $n=4$ — both confirmed by breadth-first search over the full state graph). That shape is the opposite of Pacman's, and it is why Hanoi is the standard example for "the state space is small but the tree is not".

Optimal solution length is $2^n - 1$, so the whole state space is reachable and connected: BFS from the start reaches all $3^n$ states for $n = 3$ (27) and $n = 4$ (81).

Technique: search-problem formulation, and in particular the discipline of separating the representation from the count. The exam version of this is almost always "here is a puzzle; give states, start, actions, goal test, and $|S|$".

The transferable move is the one in Step 2: ask what does the successor function actually read? Anything it never reads does not belong in the state. Anything it reads that you left out makes your formulation incomplete. Then ask what does the constraint forbid? — here the stacking rule collapsed $k!$ orderings to 1, and that collapse is the state count.

Read: Chapter 1 — Search problems, BFS/DFS/UCS, especially the state-space-size section. The Pacman formulation there is the same exercise with a different constraint doing the collapsing.

Not "is this app good or bad?". You are being asked to trace consequences through a mechanism. The grading rubric on a question like this rewards three moves, in order:

1. Name the stakeholders. Not "society" — the specific groups whose situation changes. Here at least: the driver using the app, residents of flagged areas, business owners inside flagged areas, residents of unflagged areas, the app vendor, and whoever produced the crime data.
2. Name the mechanism. A claim like "this is unfair" with no mechanism is unmarkable. A claim like "fewer cars pass the shop, so the shop loses walk-in revenue" is a mechanism, and it can be argued with.
3. Say what would change your assessment. What evidence, design change or safeguard would make the system more defensible? This is the move most answers skip and it is often worth the most.

A one-sided answer loses marks even when the side it takes is reasonable, because the question explicitly asks for both.

The direct mechanism is reduced thoroughfare. A business on a street that routing algorithms stop sending cars down loses:

• Passing trade — the customers who stop because they happened to be driving past. For a petrol station, a takeaway, a corner shop or a car wash, this can be most of the revenue.
• Discoverability — people never learn the business exists, so the loss compounds over time rather than staying flat.
• Deliverability and staffing — if navigation defaults route around an area, couriers, contractors and shift workers quietly reprice or decline trips into it.
• Property and insurance — a publicly visible "avoid" designation is a signal other pricing systems can pick up, independently of whether the underlying risk changed.

Note the asymmetry worth stating explicitly: the business owner is not a party to the decision. The driver chose to use the app and gets a benefit they wanted; the business absorbs a cost it never agreed to and often cannot even observe. That asymmetry — benefit to the chooser, cost to a non-participant — is the standard reason an individually rational feature can be collectively harmful.

A full-marks answer gives real items on both sides. The honest positives:

• Some risk is real and some users face it disproportionately. A night-shift worker, a lone driver unfamiliar with the city, or someone who has been assaulted before may value a route option that is not purely time-optimal. Dismissing that is as weak as ignoring the harms.
• Perceived safety can increase traffic overall. Visitors who would otherwise avoid an unfamiliar city entirely may travel more, which is an economic gain — though note it accrues to the unflagged areas.
• Transparency about risk is not inherently wrong. Public crime statistics already exist; an app that surfaces them is not inventing information.

The negatives:

• Concentrated economic harm, as in Step 2, falling on areas that already have less economic slack to absorb it.
• Disparate impact. In most US cities, areas with high recorded crime rates correlate strongly with historical patterns of residential segregation and disinvestment. So a feature that is written with no reference to race or income can still redistribute traffic and revenue along race and income lines. The code does not need to mention a protected attribute to act on it — a proxy is enough.
• Reputational harm that is hard to reverse. Being labelled is sticky; coming off the list requires the statistics to move, which requires the investment the label discourages.
• Residents of flagged areas are also users. They get an app that tells them their own neighbourhood is to be avoided.

A defensible verdict can go either way — "deploy with changes" is usually the strongest answer, because it forces you to name the changes. Plausible safeguards to name: make it opt-in and off by default rather than applied to every route; operate at street-and-time granularity rather than labelling whole neighbourhoods; use incident types relevant to a person in a moving car rather than all recorded crime; publish the classification so affected businesses can contest it; and audit the routing output for disparate impact rather than only auditing the inputs.

This is the part that connects the question to the rest of the course, and it is the part worth memorising as a pattern, because it recurs in predictive policing, credit scoring, hiring filters and content ranking.

recorded crime $\to$ area classified "avoid" $\to$ traffic and revenue fall $\to$ businesses close, investment leaves $\to$ conditions worsen $\to$ recorded crime rises $\to$ classification confirmed

Three properties of this loop are worth stating:

• It is self-confirming. The model's prediction changes the world in the direction of the prediction, so the model looks increasingly accurate because it was deployed. Accuracy measured after deployment is therefore not evidence that the classification was correct beforehand.
• The measurement is not neutral. "Recorded crime" is a record of reports and enforcement, not of crime. Areas that are policed more heavily record more crime at the same underlying rate, so the input already carries the history of how policing was allocated.
• Describing and causing are not separable once you act on the description. A classifier that is never used is a description. A classifier wired into millions of route decisions is an intervention, and it inherits responsibility for the outcomes it produces.

This is the general shape: a classifier trained on a record of past treatment, deployed in a way that affects future treatment, converges on justifying the past treatment.

A full-credit answer, compressed to exam length, does this:

1. Businesses: lose passing trade and discoverability as routing traffic falls; harm is concentrated and lands on parties who did not choose the feature and cannot observe it.
2. Positives: genuine safety value to some users, especially unfamiliar or vulnerable drivers; possible increase in overall travel from higher perceived safety.
3. Negatives: concentrated economic harm; disparate impact via a proxy, with no protected attribute in the code; sticky reputational damage; residents of flagged areas are harmed by a product aimed at them.
4. Mechanism: the self-confirming feedback loop in Step 4, plus the point that recorded crime measures enforcement as well as crime.
5. Position: a clear verdict with named safeguards — opt-in, finer granularity, relevant incident types, contestable and published classifications, output auditing for disparate impact.

Technique: stakeholder-and-mechanism analysis of a deployed classifier, plus recognising a feedback loop between prediction and outcome. The closest formal material on the site is the discussion of what a model is actually trained on, and the gap between training distribution and deployment distribution, in Chapter 5 — ML problem formulation; the "accuracy is not the only objective" thread continues in Chapter 12.

Part 3 is the whole problem. Parts 1, 2 and 4 exist to make part 3 possible, because you cannot construct a counterexample to an implication until you know exactly which inequality each property is.

Before anything else, compute the one quantity both definitions refer to: $h^*(n)$, the true cheapest cost from $n$ to the nearest goal. Everything is measured against it, and in an exam you will be given a small enough graph to just read these off.

Work backwards from G. Shortest distances to G (Dijkstra on the undirected graph):

Where these come from:

• $h^*(\text{D}) = 4$ via D–G directly (the alternative D–C–G costs $2 + 6 = 8$).
• $h^*(\text{C}) = 6$ — C–G directly is 6, and C–D–G is $2 + 4 = 6$ too. A tie.
• $h^*(\text{B}) = 1 + 4 = 5$ via B–D–G.
• $h^*(\text{A}) = 10$: A–C–G is $4+6=10$, A–C–D–G is $4+2+4=10$, A–D–G is $9+4=13$. So 10.
• $h^*(\text{S}) = 8$ via S–B–D–G $= 3+1+4$. Going through A costs $5 + 10 = 15$.

So the optimal solution is S → B → D → G with cost 8. Any correct heuristic must let A* find that.

The difference in one line: admissibility is a global condition checked per node against the goal; consistency is a local condition checked per edge against a neighbour. That is why consistency is strictly stronger — it constrains how fast $h$ is allowed to change as you walk, not just where it ends up.

A* always expands the frontier node with the smallest $f(n) = g(n) + h(n)$, where $g$ is the cost already paid and $h$ is the estimate of what remains. Two reference choices:

• Zero heuristic, $h \equiv 0$. Then $f = g$ and A* is literally uniform-cost search. It returns S–B–D–G, cost 8, after expanding essentially everything cheaper than 8.
• Exact heuristic, $h = h^*$. Then $f(n) = 8$ at every node on an optimal path and $f(n) > 8$ off it, so A* walks straight down S–B–D–G with no wasted expansions. This is the best any heuristic can do.

Both are admissible, so both return the optimal path — and that is the point of the question. The heuristic does not change which path an optimal algorithm returns; it changes how much of the graph you had to look at to be sure. (The exact heuristic is also consistent, as Figure 2's report confirms for every edge; the zero heuristic trivially is.)

The recipe, once you have the two definitions side by side: admissibility only caps each value from above, so you are free to make $h$ very accurate at one node and very bad at its neighbour. A big drop across a cheap edge breaks the local inequality while leaving every global cap satisfied.

Concretely: take $h = h^*$ everywhere, then knock $h(\text{D})$ down to 0.

Admissible? Yes. Every value satisfies $0 \le h(n) \le h^*(n)$ — five of them with equality and D with slack.

Consistent? No, and it fails on three edges at once, all of them edges into D:

Read the first row as the sentence it is: "from B, the heuristic claims 5 units of work remain; one step later at D it claims 0 remain; but that step only cost 1." The heuristic says you did 5 units of progress for 1 unit of cost. That is exactly what consistency forbids. Why the recipe works: dropping a value can never break admissibility (which is an upper bound), but it creates a cliff, and a cliff steeper than the edge cost is an inconsistency.

Assume $h$ is consistent and $h(n_g) = 0$ at every goal. We must show $h(n) \le h^*(n)$ for all $n$.

Setup. Fix a node $n$ and let $n = n_0 \to n_1 \to \cdots \to n_k = n_g$ be a cheapest path from $n$ to its nearest goal, so that $$h^*(n) = \sum_{i=0}^{k-1} c(n_i, n_{i+1}).$$

Induction on $k$, the number of edges remaining.

Base case $k = 0$. Then $n$ is itself a goal, $h(n) = 0 = h^*(n)$, so $h(n) \le h^*(n)$. ✓

Inductive hypothesis. Suppose the claim holds for every node whose nearest goal is reachable in $k-1$ optimal steps: in particular $h(n_1) \le h^*(n_1)$.

Inductive step. Consistency on the single edge $n_0 \to n_1$ gives $$h(n_0) \le c(n_0, n_1) + h(n_1).$$ Apply the hypothesis to $h(n_1)$: $$h(n_0) \le c(n_0, n_1) + h^*(n_1).$$ Now use the fact that the path was optimal. Because $n_0 \to n_1 \to \cdots \to n_g$ is a cheapest path from $n_0$, its tail is a cheapest path from $n_1$, so $$c(n_0, n_1) + h^*(n_1) = h^*(n_0).$$ Substituting, $h(n_0) \le h^*(n_0)$. ■

Written as the telescoping sum instead, the same argument in one line: adding $h(n_i) - h(n_{i+1}) \le c(n_i, n_{i+1})$ over $i = 0, \dots, k-1$ gives $$h(n_0) - \underbrace{h(n_k)}_{=\,0} \le \sum_{i=0}^{k-1} c(n_i,n_{i+1}) = h^*(n_0).$$

The converse is false, which is what Step 5 constructed. So consistent $\Rightarrow$ admissible, and the implication is strict.

Technique: the admissibility/consistency distinction, and the ability to construct a counterexample to a one-directional implication. The exam version is usually "is this heuristic admissible / consistent / neither, and justify" — which you answer by checking one inequality per node for admissibility and one inequality per edge for consistency. There is no shortcut and there does not need to be; these graphs are small.

The reason the distinction is worth marks at all: admissibility is enough for A* tree search to be optimal, but graph search (with an explored set) needs consistency. Problem 1.5(f) below is a concrete graph where admissible-but-inconsistent makes A* graph search return a suboptimal path.

Read: Chapter 2 — Heuristics, Greedy and A*.

Not "find the best path" — the point is to watch five different frontier orderings produce five different behaviours on identical data. Three conventions decide every answer, so pin them down first:

• Goal test on pop, not on generation. This is why Greedy's explored set contains only A: E gets generated, then popped, and the search stops before E is ever "explored".
• Graph search: there is an explored set, and a node already explored is never expanded again.
• Alphabetical tie-breaking on the frontier, applied after the algorithm's own priority.

The frontier priority for each: DFS = deepest first; BFS = shallowest first; UCS = smallest $g$; Greedy = smallest $h$; A* = smallest $g + h$.

Pop A (not a goal) → explored {A}. Children: C, D, E, all at depth 1. Deepest-first with alphabetical tie-break pops C.

C is not a goal → explored {A, C}. Children F, G at depth 2. Deepest first, alphabetical: pop F.

F not a goal → explored {A, C, F}. Child B at depth 3. Pop B (deepest).

B not a goal → explored {A, C, F, B}. B's only child is C, already explored, so nothing is added. The frontier now holds A-C-G (depth 2), A-D (depth 1), A-E (depth 1). Deepest is G — a goal. Stop.

Explored: A, C, F, B   ·   Path: A → C → G   ·   cost 5

DFS dove into a dead-end branch (F, B) that leads nowhere new, and returned a path costing 5 when a cost-2 path existed. It also never looked at D, which is on the optimal path.

Pop A → explored {A}; frontier C, D, E all at depth 1. Shallowest first, so the whole of depth 1 goes before any of depth 2; alphabetical within the level.

Pop C (not a goal) → explored {A, C}; adds F, G at depth 2.

Pop D (not a goal) → explored {A, C, D}; adds G at depth 2.

Pop E — a goal, at depth 1. Stop.

Explored: A, C, D   ·   Path: A → E   ·   cost 3

BFS found the shallowest goal, exactly as advertised: one edge. Shallowest is not cheapest — cost 3 against the optimum of 2. This is the cleanest one-line demonstration on the page that BFS optimises depth, not cost.

Pop A at $g=0$ → explored {A}. Frontier by $g$: D 1, C 2, E 3.

Pop D ($g=1$, not a goal) → explored {A, D}; adds A-D-G at $g = 1 + 1 = 2$.

Frontier: C 2, G 2, E 3. Tie at 2 between C and G — alphabetical, so pop C (not a goal) → explored {A, D, C}; adds F at $g=4$ and a second route to G at $g=5$ (worse, discarded).

Frontier: G 2, E 3, F 4. Pop G at $g=2$ — a goal. Stop.

Explored: A, D, C   ·   Path: A → D → G   ·   cost 2

Optimal, as UCS always is with non-negative costs. Note it paid for that with one extra expansion (C) that A* will avoid.

Greedy best-first orders the frontier by $h$ alone, ignoring $g$ entirely.

Pop A → explored {A}. Frontier with $h$: C 1, D 1, E 0. Smallest $h$ is E. Pop E — a goal. Stop.

Explored: A   ·   Path: A → E   ·   cost 3

One expansion — the cheapest search on the page — and a suboptimal answer, cost 3 against 2. Greedy took the bait: E is a goal and $h(\text{E}) = 0$, but reaching it costs 3 while D's cheaper route costs 2 in total. Greedy cannot see that because it never looks at $g$.

A* orders by $f = g + h$.

Pop A ($f = 0+2 = 2$) → explored {A}. Frontier: C $f = 2+1 = 3$, D $f = 1+1 = 2$, E $f = 3+0 = 3$.

Pop D ($f = 2$, not a goal) → explored {A, D}; adds G at $f = 2 + 0 = 2$.

Frontier: C 3, E 3, G 2. Pop G at $f = 2$ — a goal. Stop.

Explored: A, D   ·   Path: A → D → G   ·   cost 2

Optimal and cheaper than UCS — 2 expansions instead of 3, because $h$ told it that C was not worth opening.

Takeaway, one line per algorithm: DFS optimises nothing and got the worst answer; BFS optimises depth and found a 1-edge path that costs more than a 2-edge one; Greedy optimises the estimate of what is left and threw away the cost already paid; UCS optimises cost paid so far and is correct but does extra work; A* optimises their sum and is correct with the least work of the two correct ones.

Notice the ranking of explored-set sizes — Greedy 1, A* 2, BFS 3, UCS 3, DFS 4. Cheap does not mean good and expensive does not mean good. The only pair you can compare fairly is UCS versus A*, because they both return the optimum; there A* strictly wins, and that is the entire argument for having heuristics.

Technique: hand-simulating the five uninformed and informed search strategies with an explicit explored set and a stated tie-break rule. Nearly every exam has one of these, and nearly all lost marks come from convention slips rather than from misunderstanding the algorithms: testing for the goal on generation instead of on pop, forgetting the explored set, or dropping a frontier entry that should still be live.

Read: Chapter 1 for DFS/BFS/UCS and Chapter 2 for Greedy and A*.

Each item is an "always" claim, so there are only two kinds of correct answer: a proof that it holds in general, or a single concrete instance where it fails. Four of these six are false, and for each of those a three-node graph is enough. Learning to reach for the smallest possible counterexample is the skill being tested.

Watch for the two words that make a claim fragile: "always" and "implies". Both are universally quantified, so one example kills them.

False.

DFS has no guarantee of expanding many nodes — it has no guarantee at all. If the goal happens to lie at the end of the first branch DFS picks, it expands exactly the $d$ nodes on that path and stops. Meanwhile A*, being complete and optimal, must expand every node whose $f$-value is strictly less than the optimal cost before it can certify the answer. If several such nodes exist off the lucky branch, A* expands more.

Problem 1.4 above is almost this: Greedy expanded 1 node, A* expanded 2, and Greedy's answer was worse. The general statement: being optimal costs work, and a lucky unguided search can beat a correct guided one on any single instance. What A* guarantees is the answer, not a node-count bound against DFS.

False. Manhattan distance overestimates, which is the direction admissibility forbids.

Counterexample: on an empty board, a rook goes from one corner to the opposite corner of a $4 \times 4$ region in 2 moves (along a row, then along a column). Manhattan distance between those squares is $3 + 3 = 6$. Since $6 > 2$, the heuristic overestimates and is not admissible.

The reason is a units mismatch: Manhattan distance counts squares travelled, but the cost function counts moves, and one rook move covers arbitrarily many squares. An admissible heuristic here is the far cruder "0 if same square, 1 if same row or column, else 2" — and on an empty board that is exact. Whenever a heuristic looks wrong, check first whether it is measuring the same thing the cost function charges for.

True.

Pacman moves on a grid, one square per unit cost, only horizontally or vertically. A straight line is the shortest distance between two points in the plane, so the Euclidean distance can never exceed the length of any route — in particular it cannot exceed the shortest legal grid route. Hence $0 \le h(n) \le h^*(n)$.

The two cases, explicitly:

• Goal in the same row or column, no walls: Euclidean distance equals the true cost. Tight, still admissible.
• Goal diagonally offset: Euclidean distance is $\sqrt{\Delta x^2 + \Delta y^2}$, strictly less than the grid cost $\Delta x + \Delta y$. A loose underestimate.

Walls only ever make the true cost larger, which widens the gap and keeps admissibility. The general pattern: relaxing the problem until it is trivially solvable gives an admissible heuristic — here the relaxation is "let Pacman fly in a straight line through walls".

False. Two underestimates can easily add up to an overestimate.

Counterexample on a 3-node path graph, S → A cost 4, A → B cost 6, goal B:

$h_1$ and $h_2$ are each admissible ($7 \le 10$, $8 \le 10$, $4 \le 6$, $5 \le 6$). Their sum gives 15 at S where the truth is 10, and 9 at A where the truth is 6. Not admissible.

But the maximum is safe: $\max(h_1, h_2) \le h^*$ whenever both are, since the max of two numbers each $\le h^*$ is $\le h^*$. So when you have several admissible heuristics, take the max, never the sum — and note the max is at least as informative as either one, so this is a free improvement. (Sums are admissible in the special case where the heuristics are disjoint, i.e. each accounts for cost the others do not; that is how pattern databases are combined, and it is a property you have to prove, not assume.)

False. The implication runs the other way only — see the proof in Problem 1.3, Step 6.

Smallest counterexample: path graph S → A cost 1, A → B cost 3, goal B.

Admissible: $4 \le 4$, $1 \le 3$, $0 \le 0$. Inconsistent on the edge S → A: we need $h(\text{S}) \le c(\text{S},\text{A}) + h(\text{A})$, i.e. $4 \le 1 + 1 = 2$. It fails.

Read it as a sentence: the heuristic claims 4 units remain at S and only 1 unit remains at A, so it claims 3 units of progress were made — across an edge that cost 1. The heuristic's step estimate $h(\text{S}) - h(\text{A}) = 3$ overestimates the real step cost of 1. The triangle inequality is violated, and Problem 1.3 Step 5 is the same trick on a bigger graph.

False, and this is the item worth the most, because it is the reason consistency exists as a concept at all.

Counterexample. Four nodes, goal C, edges S→A 1, S→B 3, A→B 1, B→C 2. Heuristics $h(\text{S}) = 4$, $h(\text{A}) = 3$, $h(\text{B}) = 0$, $h(\text{C}) = 0$.

First, admissibility: true costs to C are $h^*(\text{S}) = 4$ (via S-A-B-C $= 1+1+2$), $h^*(\text{A}) = 3$, $h^*(\text{B}) = 2$, $h^*(\text{C}) = 0$. So $4 \le 4$, $3 \le 3$, $0 \le 2$, $0 \le 0$ — admissible. The optimal path is S → A → B → C, cost 4.

Now run A* graph search:

1. Pop S. Frontier: S-A with $f = 1 + 3 = 4$; S-B with $f = 3 + 0 = 3$.
2. Smallest $f$ is 3, so pop B at $g = 3$ and mark B explored. Adds B-C at $f = 5 + 0 = 5$.
3. Frontier: A $f=4$, C $f=5$. Pop A at $g = 1$. A's successor is B — but B is already in the explored set, so the edge A→B is discarded and the cheaper route to B at $g = 2$ is never recorded.
4. Frontier: C $f = 5$. Pop C. Return S → B → C, cost 5.

Cost 5, not 4. A* graph search returned a suboptimal path with an admissible heuristic.

The mechanism, stated so you can recognise it: $h(\text{B}) = 0$ was a severe underestimate, which pulled B's $f$-value down and got B popped early via an expensive route. The explored set then froze that mistake in place. Checking consistency confirms the diagnosis — the edge A→B requires $h(\text{A}) \le c(\text{A},\text{B}) + h(\text{B})$, i.e. $3 \le 1 + 0 = 1$, which fails.

Technique: counterexample construction. Four of six are false and every counterexample fits in three or four nodes. The habit to build: when a claim says "always", spend ten seconds trying to break it before trying to prove it — on this course the broken ones outnumber the true ones.

Read: Chapter 1 for (a), Chapter 2 for (b)–(f), especially the admissibility/consistency section and the tree-vs-graph-search discussion that (f) turns on.

You are being asked to simulate a recursion, so the only way to get it right is to be strict about what $\alpha$ and $\beta$ mean:

• $\alpha$ = the best (highest) value MAX can already guarantee somewhere on the path from the root to the current node. It starts at $-\infty$ and only ever increases, and only at MAX nodes.
• $\beta$ = the best (lowest) value MIN can already guarantee on that path. Starts at $+\infty$, only decreases, only at MIN nodes.

Both are inherited down the tree and updated locally. The two cutoff rules:

Each rule says the same thing in different voices: "the player above me already has an option at least this good, so nothing I find here can change their mind."

Enter B with the root's $(\alpha, \beta) = (-\infty, +\infty)$.

B₁ (MAX), inherits $(-\infty, \infty)$. Reads 3 ($v = 3$, $\alpha = 3$), then 5 ($v = 5$, $\alpha = 5$). Neither triggers $v \ge \beta = \infty$. Returns 5. Finishes with $\alpha = 5, \beta = \infty$.

Back at B: $v = 5$, so $\beta \leftarrow 5$. Is $v \le \alpha = -\infty$? No. Continue.

B₂ (MAX), inherits $(\alpha, \beta) = (-\infty, 5)$ — note it gets B's updated $\beta$, which is the whole point. Reads 6: $v = 6$, $\alpha \leftarrow 6$. Check the cutoff: $v = 6 \ge \beta = 5$, so prune — the second leaf (value 2) is never read. Returns 6, with $\alpha = 6, \beta = 5$.

Why that prune is sound, in MIN's voice: "B₂ can already get 6, so B₂ is worth at least 6. I am a minimizer and I already have an option worth 5. Whatever else is in B₂, I will not choose it."

Back at B: $v = \min(5, 6) = 5$, $\beta = 5$. B returns 5 with $(\alpha, \beta) = (-\infty, 5)$. Root: $v = 5$, $\alpha \leftarrow 5$.

Enter C with $(\alpha, \beta) = (5, \infty)$ — $\alpha = 5$ because the root has already banked B's 5.

C₁ (MAX), inherits $(5, \infty)$. Reads 8 ($v = 8$, $\alpha = 8$; cutoff needs $v \ge \infty$, no), then 1 ($v$ stays 8). Returns 8, $\alpha = 8, \beta = \infty$.

Back at C: $v = 8$, $\beta \leftarrow 8$. Is $8 \le \alpha = 5$? No. Continue.

C₂ (MAX), inherits $(5, 8)$. Reads 9: $v = 9$, $\alpha \leftarrow 9$. Cutoff: $9 \ge \beta = 8$ → prune, the leaf 4 is never read. Returns 9, $(\alpha, \beta) = (9, 8)$.

Back at C: $v = \min(8, 9) = 8$, $\beta = 8$. C returns 8 with $(\alpha, \beta) = (5, 8)$. Root: $v = \max(5, 8) = 8$, $\alpha \leftarrow 8$.

Enter D with $(\alpha, \beta) = (8, \infty)$.

D₁ (MAX), inherits $(8, \infty)$. Reads 7 ($v = 7$; $\alpha$ stays 8 since $\max(8,7) = 8$), then 0 ($v$ stays 7). Returns 7.

Back at D: $v = 7$, $\beta \leftarrow 7$. Check the MIN cutoff: $v = 7 \le \alpha = 8$ → prune. The entire D₂ subtree — a MAX node and both of its leaves — is never visited.

In the root's voice: "D is a minimizer and it can already hold me to 7. I already have 8 from C. Nothing inside D can get me above 7, so D is dead to me."

D returns 7 with $(\alpha, \beta) = (8, 7)$. Root: $v = \max(8, 7) = 8$, and MAX's cutoff needs $v \ge \beta = \infty$, which never fires at the root.

Root returns 8, and the move it recommends is "go to C".

Leaves read: 8 of 12. Pruned: the 2 under B₂, the 4 under C₂, and both of D₂'s leaves (2 and 6).

Takeaway. Three things you can carry to any alpha-beta question:

• Pruning never changes the root value. It changes some internal values into bounds. Here D's true minimax value is 6 and alpha-beta reported 7 — a legitimate bound, and harmless because 7 was already below $\alpha = 8$.
• Every prune is the same sentence. "The player one level up already has something at least this good." If you can say that sentence out loud at the node you are pruning, the prune is right.
• $\alpha$ grows only at MAX nodes, $\beta$ shrinks only at MIN nodes, and both are inherited. The single most common hand-trace error is updating the wrong one, or failing to pass the updated value down to the next child.

Technique: hand-simulating alpha-beta with explicit bound bookkeeping. Read: Chapter 3 — Minimax, $\alpha$-$\beta$, Expectimax.

Both items compare two numbers computed from two trees, and (b) adds a third thing: a policy transplanted between them. Keeping those three ideas separate is the whole problem. Specifically distinguish:

• the value of a tree — what you get if you play optimally against that particular opponent model;
• the policy — the move you choose at each node;
• what a guarantee means — a worst-case floor, versus an average.

True.

The argument is a single inequality applied bottom-up. At any node that was a MIN node and is now a chance node with children values $v_1, \dots, v_m$ and probabilities $p_1, \dots, p_m$:

$\displaystyle \min_i v_i \;\le\; \sum_i p_i v_i$

because a weighted average of numbers (weights non-negative, summing to 1) can never fall below the smallest of them. So replacing MIN with expectation weakly increases the value at that node. MAX is monotone — raising a child's value can only raise or hold the max — so the increase propagates up the tree without reversing. Hence $V_M \le V_E$.

In words: minimax assumes the worst possible opponent. A randomising opponent is, by definition, no worse than the worst. Playing against a weaker opponent can only help you. Equality happens exactly when every chance node puts all its probability on its own minimum child — i.e. when the "random" opponent is in fact playing optimally against you.

False, and for two independent reasons. Either one is enough to answer.

Reason 1 — the minimax policy is the wrong policy for the chance game. Minimax chooses the action whose worst case is best, so it will refuse an action with a catastrophic but unlikely branch. Expectimax chooses the action whose average is best, so it takes that gamble when the average pays. Those are different actions in general, and $V_E$ is by definition the value of the expectimax policy. Playing a different policy gets you the value of that policy, which is at most $V_E$ and typically strictly less.

Concretely: offered a guaranteed 1, or a coin flip between 100 and $-1$, minimax takes the guaranteed 1 (worst cases 1 versus $-1$) while expectimax takes the flip (expected value 49.5). The expectimax value of the tree is 49.5; the minimax policy delivers 1.

Reason 2 — "at least" is the wrong kind of claim about an expectation. Even if you did play the expectimax policy, $V_E$ is an average over the chance outcomes. On any single playthrough you can land on a bad branch and score far below $V_E$. An expectation is not a floor. Minimax values are floors (that is what makes them guarantees); expectimax values are not.

So the claim fails both on which policy and on what kind of promise a value is.

(a) True — $\min \le$ weighted average, applied at every converted node and propagated through monotone MAX.

(b) False — the minimax policy is risk-averse and so generally differs from the expectimax policy; and in any case an expectation is not a worst-case guarantee.

Technique: reasoning about values versus policies, and about the difference between worst-case and expected-case guarantees. Read: Chapter 3, the expectimax section.

Part (a) is mechanical. Parts (b) and (c) are the real question, and they are about one idea: pruning requires a bound.

At a MIN node you get a bound for free — one child's value already caps the node, because MIN will take at most that. At a chance node you get nothing for free: the node's value is an average, and until you have seen every child, any unseen child could be arbitrarily large and drag the average arbitrarily high. So a chance node is only prunable when something external caps the unseen children. That external thing is the leaf bound in part (c).

Expectimax values are computed child-by-child, so for each node: multiply each child's value by its probability and add.

Bottom up. The MAX nodes just take maxima:

Then the chance nodes take expectations:

$P = \tfrac12 (14) + \tfrac12 (10) = 7 + 5 = \mathbf{12}$

$Q = \tfrac34 (3) + \tfrac14 (8) = \tfrac94 + 2 = \tfrac{17}{4} = \mathbf{4.25}$

And the root is a maximizer: $\max(12, 4.25) = \mathbf{12}$, choosing P.

Note that no node here is a minimizer. The value 12 is therefore not a guarantee — play P and you get 14 or 10, each half the time, averaging 12. The specific number 12 never actually occurs.

No. Not a single node.

Here is the argument, and it is worth being able to state it crisply because it is the standard exam answer.

Suppose we have finished P (value 12) and are partway through Q, having evaluated Q₁ $= 3$. Can we skip Q₂? Only if we can show $Q \le 12$ without looking. But

$Q = \tfrac34(3) + \tfrac14 (\text{Q}_2) = 2.25 + 0.25\,\text{Q}_2$

and if Q₂ is unbounded above then so is $Q$. Setting $Q$'s leaf 8 to, say, $10^6$ would make $Q = 250{,}002.25$ and change the root's answer. Since nothing in the problem rules that out, we are obliged to look.

The same reasoning blocks pruning inside the MAX nodes: at P₁, after reading 14, we cannot skip the second leaf, because a MAX node needs a $\beta$ from above to cut against — and there is no minimizer anywhere in this tree, so $\beta$ is $+\infty$ everywhere.

This is why alpha-beta has no direct expectimax analogue, and why game-playing programs that face randomness (backgammon, poker) lean on sampling and evaluation functions rather than on exact pruning.

The bound is what unlocks pruning: an unseen subtree can now be no better than $+20$, so a partial expectation gives a genuine optimistic ceiling.

Visit left to right.

P: Can we prune inside P? After P₁ $= 14$, the optimistic ceiling on P is $\tfrac12 (14) + \tfrac12 (20) = 17$. We have no better alternative banked yet ($\alpha = -\infty$ at the root), so 17 beats nothing and we must continue. P₂ $= 10$, and $P = 12$. Root banks $\alpha = 12$.

Q: Evaluate Q₁ $= 3$ (both its leaves, since there is nothing to cut against inside it). Now compute Q's optimistic ceiling, assuming the unseen Q₂ comes back at the maximum possible $+20$:

$Q \;\le\; \tfrac34(3) + \tfrac14(20) \;=\; 2.25 + 5 \;=\; \mathbf{7.25}$

And $7.25 \le \alpha = 12$. So prune Q₂ — the MAX node and both its leaves (8 and 1) are never visited. Q returns the bound 7.25 rather than its true value 4.25, which does not matter because both are below 12.

Root returns 12, choosing P. 6 of 8 leaves were read.

Notice how fragile this is, and drag the slider in Figure 5 to feel it. The prune needs $\tfrac34(3) + \tfrac14 M \le 12$, i.e. $M \le 39$. With leaves bounded by $\pm 40$ instead of $\pm 20$, the ceiling is $2.25 + 10 = 12.25 > 12$ and nothing gets pruned. And the $\tfrac14$ weight is doing much of the work: if Q's probabilities were $\tfrac12, \tfrac12$ the ceiling at $M = 20$ would be $11.5$ — still a prune, but only just. The tighter the bound and the smaller the unseen probability mass, the more you can prune.

(a) P₁ $=14$, P₂ $=10$, Q₁ $=3$, Q₂ $=8$; chance nodes $P = 12$, $Q = 4.25$; root $= 12$, choosing P.

(b) Nothing is prunable. Unbounded leaves mean an unseen child of a chance node can be arbitrarily large, so no partial expectation bounds the node; and with no MIN node anywhere, $\beta = +\infty$ throughout, so the MAX nodes have nothing to cut against either.

(c) With leaves in $[-20, 20]$: after Q₁ $= 3$, the ceiling on Q is $7.25 \le 12$, so Q₂ and its two leaves are pruned. Root still 12; 6 of 8 leaves read.

Takeaway. Pruning is not a property of an algorithm, it is a property of information. Alpha-beta prunes because MIN and MAX hand each other bounds for free. Chance nodes hand out nothing, so expectimax prunes only when you are given a bound from outside — and then only by exactly as much as the bound is tight.

Technique: expectimax evaluation and bound-based pruning at chance nodes. Read: Chapter 3, the expectimax and pruning sections.

These look like definition recall and they are not. Each has a one-sentence answer that earns full marks, and a longer answer that earns full marks and also predicts the next exam question. The one-sentence versions:

• (a) Same operation, different scope: forward checking enforces arc consistency once, only on the arcs into the just-assigned variable; AC-3 keeps going until nothing changes anywhere.
• (b) MRV answers "which variable next?" and the answer is "the one most likely to fail", because failing early prunes more.
• (c) LCV answers "which value first?" and the answer is "the one most likely to succeed", because you only need one solution.

Notice that MRV and LCV point in opposite directions — one seeks failure, the other avoids it. That is the single most commonly misstated thing about them, so Step 4 explains why it is not a contradiction.

Both do the identical primitive operation, revise an arc: for a directed arc $X \to Y$, delete from $D_X$ every value with no consistent partner left in $D_Y$. Values die in the tail. They differ only in which arcs they revise and when they stop.

So: forward checking is one iteration of AC-3's inner loop, with no propagation. AC-3 propagates.

The consequence that exams test: forward checking can miss a failure that is already logically certain. If two neighbouring variables both get reduced to the same single value, the problem is dead — but forward checking only ever looks outward from the assigned variable, so it never compares those two neighbours with each other and reports no failure. AC-3 would revise the arc between them and empty a domain. Chapter 4 works a concrete instance of exactly this.

MRV = choose the unassigned variable with the fewest remaining legal values. Also called "most constrained variable", and informally fail-fast.

Two justifications, and a good answer gives both:

• You have to assign every variable anyway. Unlike path search, there is no choice about which variables appear in the answer — all $n$ of them do, and every solution sits at depth $n$. So the ordering is free: it costs nothing to do the hard ones first. Given that it is free, do the thing that helps.
• Failing early prunes exponentially more. A variable with 1 remaining value has branching factor 1; a variable with $d$ has branching factor $d$. Putting the small branching factors near the root of the search tree makes the whole tree smaller. And if a variable has zero remaining values, MRV finds that immediately and you backtrack at depth $k$ instead of discovering it at depth $n$ after $d^{\,n-k}$ wasted assignments.

The slogan: if this branch is doomed, I want to know now, not after I have filled in the easy variables.

LCV = among the values left for the chosen variable, try the one that rules out the fewest values in neighbouring domains. In practice: for each candidate value, run forward checking, sum the sizes of the neighbours' surviving domains, and pick the value with the largest sum.

The justification: we only need one solution, and we are not going to try all $d^n$ combinations. So the value we try first should be the one most likely to lead somewhere — and "leaves the most options open downstream" is a decent proxy for that. If it works, we never try the others at all.

One honest caveat: LCV is a heuristic in the weak sense, and it costs real work to evaluate (one forward-checking pass per candidate value). On problems with no solution it is pure overhead, since every value fails and the ordering is irrelevant. MRV, by contrast, helps on satisfiable and unsatisfiable instances alike. Problem 2.7 below measures both on a tiny instance.

(a) Same revise operation; forward checking does one layer (arcs into the just-assigned variable) and stops, AC-3 propagates to a fixpoint over the whole graph. FC is cheap and can miss already-certain failures; AC-3 is $O(nd^3)$ and cannot.

(b) MRV picks the next variable: fewest remaining values, because all variables must be assigned anyway, so ordering is free — and small branching factors near the root plus immediate detection of empty domains shrink the tree.

(c) LCV picks the next value: the one deleting least from neighbours, because only one solution is needed and the first value tried should be the most promising.

Technique: knowing what each piece of CSP machinery is for, not just what it does. Read: Chapter 4 — Constraint Satisfaction, the filtering and ordering sections.

Four separate skills, which is why this is the most exam-like problem in the recitations:

1. (a) Formulation, with the specific demand that constraints be symbolic. "No two planes share a slot" earns fewer marks than $\text{slot}(X) \neq \text{slot}(Y)$.
2. (b) Recognising that a change in the constraints can shrink the domain, because information moved from the value into the variable's identity.
3. (c) AC-3 by hand, to a fixpoint.
4. (d) Backtracking with MRV + forward checking, with the undone assignments shown — they are the marks.

A trap in (c)/(d): arc consistency and backtracking are different procedures and part (d) explicitly says to start from the unary-filtered domains, not from the AC-3 output of part (c). If you carry (c)'s domains into (d) you will get a shorter trace and lose the marks for the backtrack.

Variables: one per plane — $A, B, C, D, E$. (Not one per slot. Choosing variables = planes is what makes the "at most one reservation each" requirement automatic, since a variable holds exactly one value.)

Domains: each variable takes a pair

$D_X = \{\text{intl}, \text{dom}\} \times \{1,2,3,4\}$,   so $|D_X| = 8$.

Write $X[0]$ for the runway component and $X[1]$ for the slot component of the pair assigned to $X$.

Constraints. Unary:

$B[1] = 1 \qquad D[1] \ge 3 \qquad A[1] \le 2$

Binary:

$D[1] < C[1]$

$X \neq Y \quad \text{for all pairs } X \neq Y \in \{A,B,C,D,E\}$

where the last line compares the whole pairs — two planes may share a slot if they are on different runways, and may share a runway if they are in different slots, but not both. It is an all-different constraint over 5 variables, which decomposes into $\binom{5}{2} = 10$ binary constraints.

Now A, B, C are forced onto the international runway and D, E onto the domestic one. The runway component of every variable's value is therefore determined by which variable it is, so carrying it inside the value is redundant. Drop it:

Variables: $A, B, C, D, E$.    Domain: $\{1, 2, 3, 4\}$ for every variable.

This is worth pausing on, because it is a general modelling move: information that is constant per variable belongs in the variable, not in the domain. The domain shrank from 8 values to 4, which halves the branching factor at every node of the search tree.

The constraints change too. The slot-collision constraint now applies only within a runway:

• International runway: $A \neq B$, $A \neq C$, $B \neq C$ — a triangle.
• Domestic runway: $D \neq E$ — a single edge.
• Cross-runway: $D < C$ survives, because it is about time, not about runway occupancy. This is the only edge joining the two groups.
• Unary, unchanged: $B = 1$, $D \ge 3$, $A \le 2$.

Note what vanished: there is no longer any constraint between A and D, or between B and E, and so on — planes on different runways cannot collide. Six of the original ten binary constraints disappear.

Unary constraints first. These are not arcs; just apply them directly.

Now revise arcs, re-queueing a variable's other arcs whenever its domain shrinks. The propagation, in a convenient order (AC-3's fixpoint does not depend on the order):

1. $A \to B$: $A = 1$ has no partner, since $D_B = \{1\}$ and $1 \neq 1$ is false. Delete 1.   $D_A = \{2\}$.
2. $C \to B$: $C = 1$ has no partner in $\{1\}$. Delete 1.   $D_C = \{2,3,4\}$.
3. $C \to A$: $D_A = \{2\}$ now, so $C = 2$ has no partner. Delete 2.   $D_C = \{3,4\}$.
4. $C \to D$: the constraint is $D < C$, so $C = c$ needs some $d \in \{3,4\}$ with $d < c$. For $c = 3$: no $d < 3$ remains. Delete 3. For $c = 4$: $d = 3$ works, keep.   $D_C = \{4\}$.
5. $D \to C$: $D = d$ needs some $c \in \{4\}$ with $d < c$. $d = 3$: $3 < 4$ ✓. $d = 4$: no. Delete 4.   $D_D = \{3\}$.
6. $E \to D$: $E = e$ needs some $d \in \{3\}$ with $e \neq d$. $e = 3$ fails. Delete 3.   $D_E = \{1,2,4\}$.
7. Everything re-queued now revises to no change: $B \to A$, $A \to C$, $B \to C$, $C \to D$ again, $D \to E$ all leave domains alone. Queue empties.

$D_A = \{2\}$,   $D_B = \{1\}$,   $D_C = \{4\}$,   $D_D = \{3\}$,   $D_E = \{1, 2, 4\}$

Four of the five variables are now pinned to a single value, before any assignment has been made. Brute-forcing all $4^5 = 1024$ assignments confirms the CSP has exactly 3 solutions — $(A,B,C,D,E) = (2,1,4,3,1)$, $(2,1,4,3,2)$ and $(2,1,4,3,4)$ — and they differ only in $E$, exactly matching the three values AC-3 left in $D_E$.

Reset to the post-unary domains: $A\{1,2\}$, $B\{1\}$, $C\{1,2,3,4\}$, $D\{3,4\}$, $E\{1,2,3,4\}$. At each step pick the unassigned variable with the fewest values (ties → earlier letter), try its values in increasing order, and forward check.

1. (B, 1). B has 1 value — MRV picks it. Forward check on B's neighbours A and C: delete 1 from each. $A\{2\}$, $C\{2,3,4\}$. No empty domain.
2. (A, 2). MRV: $A$ has 1, $D$ has 2, $C$ has 3, $E$ has 4. Assign $A = 2$. Forward check on C (A's only unassigned neighbour): delete 2. $C\{3,4\}$.
3. (C, 3). MRV: $C$ has 2, $D$ has 2, $E$ has 4 — tie between C and D, broken by letter, so C. Lowest value first: $C = 3$. Forward check on D via $D < C$: D's values must be $< 3$, but $D = \{3,4\}$, so $D_D = \varnothing$ — failure. Undo.
4. (C, 4). Next value for C. Forward check: D needs $d < 4$, so $D\{3,4\} \to \{3\}$. Non-empty, continue.
5. (D, 3). MRV: $D$ has 1, $E$ has 4. Assign $D = 3$. Forward check on E: delete 3. $E\{1,2,4\}$.
6. (E, 1). Only E left; lowest value. Complete and consistent. Done.

(B, 1),  (A, 2),  (C, 3),  (C, 4),  (D, 3),  (E, 1)

Six assignments tried, one of them retracted. Final solution $A=2, B=1, C=4, D=3, E=1$ — one of the three the brute-force enumeration found.

(a) Variables = planes; domain = $\{\text{intl},\text{dom}\} \times \{1,2,3,4\}$; unary $B[1]=1$, $D[1]\ge3$, $A[1]\le2$; binary $D[1] < C[1]$ and all 10 pairs $X \neq Y$ on whole (runway, slot) pairs.

(b) Domain collapses to $\{1,2,3,4\}$; graph = triangle A-B-C, edge D-E, single bridge C-D carrying $D < C$.

(c) $A\{2\}$, $B\{1\}$, $C\{4\}$, $D\{3\}$, $E\{1,2,4\}$ — which exactly brackets the 3 solutions.

(d) (B,1), (A,2), (C,3), (C,4), (D,3), (E,1) — one backtrack, at C.

Takeaway. Compare (c) and (d) directly. AC-3 pinned four variables and cost one propagation pass with no search at all; MRV + forward checking searched and hit a dead end, because forward checking from $C = 3$ could see D's domain emptying but could never have predicted it in advance. That is the trade the chapter is about: filtering harder means searching less, and which side is cheaper depends on the instance.

Technique: full CSP pipeline — formulation, domain design, constraint graph, AC-3, MRV with forward checking. Read: Chapter 4 end to end; this problem touches almost every section of it.

The hint not to create variables for filled squares is doing real work: it means every row, column and diagonal contains at most two variables, so every sum constraint is unary or binary and the CSP needs no higher-arity constraints at all. That is the design insight the problem is built around.

So the method is: write down all eight sum equations (3 rows, 3 columns, 2 diagonals), then sort them by how many variables they contain. The ones with a single variable are unary constraints that pin a value outright. The ones with two are binary edges.

Variables: $A, B, C, D, E$ — one per blank square.

Domain: the digits not already used. Given $\{4, 2, 5, 6\}$ are placed, the remaining five are

$D_X = \{1, 3, 7, 8, 9\}$ for every variable.

The eight sum equations, each simplified:

Plus the all-different constraint: $A, B, C, D, E$ pairwise distinct (10 binary constraints, ignored in the graph by instruction).

So the constraints in symbols: unary $A = 9$, $C = 7$, $D = 8$; binary $B + C = 10$, $D + E = 9$, $B + D = 11$, $A + E = 10$; plus all-different. Note the main diagonal gives a free consistency check on the given numbers rather than a constraint — worth mentioning in an answer, because noticing that a line has zero variables is the same skill as noticing it has one.

Drop the three unary constraints (they are node-level) and the all-different (by instruction). Four binary constraints remain, and each joins exactly two variables:

• $A + E = 10$ — A and E share column 2. Edge A–E.
• $D + E = 9$ — D and E share row 3. Edge E–D.
• $B + D = 11$ — B and D share column 1. Edge D–B.
• $B + C = 10$ — B and C share row 2. Edge B–C.

Four edges on five nodes with no cycle: the graph is a path, $A - E - D - B - C$. That is a structurally easy CSP — a tree-shaped constraint graph can be solved without any backtracking at all, by arc-consistency plus a single sweep. See Figure 7.

Unary first. Three variables are fully determined:

$D_A = \{9\}$,   $D_C = \{7\}$,   $D_D = \{8\}$,   $D_B = D_E = \{1,3,7,8,9\}$

Then the arcs. Queue the four arcs pointing at the already-pinned variables, since only those can delete anything:

1. $E \to A$ with $A + E = 10$: $E = e$ needs $10 - e \in D_A = \{9\}$, so $e = 1$ only. Delete 3, 7, 8, 9.   $D_E = \{1\}$. Re-queue $A \to E$, $D \to E$.
2. $B \to C$ with $B + C = 10$: $B = b$ needs $10 - b \in D_C = \{7\}$, so $b = 3$ only. Delete 1, 7, 8, 9.   $D_B = \{3\}$. Re-queue $C \to B$, $D \to B$.
3. $B \to D$ with $B + D = 11$: $D_B = \{3\}$ and $11 - 3 = 8 \in D_D$. ✓ No change.
4. $E \to D$ with $D + E = 9$: $D_E = \{1\}$ and $9 - 1 = 8 \in D_D$. ✓ No change.
5. $A \to E$, $D \to E$, $C \to B$, $D \to B$: all already consistent. Queue empties.

Every domain is a singleton, so arc consistency has solved the CSP outright:

$A = 9$,   $B = 3$,   $C = 7$,   $D = 8$,   $E = 1$

Filling in the grid:

All three rows, all three columns and both diagonals check out, all nine digits appear once, and exhaustive search over the $5! = 120$ orderings of $\{1,3,7,8,9\}$ confirms this is the only solution. The all-different constraint, which we were told to ignore, happens to be satisfied for free — worth noting, because in general ignoring a constraint during filtering means you must verify it at the end.

(a) Variables $A..E$, domain $\{1,3,7,8,9\}$; unary $A=9$, $C=7$, $D=8$; binary $B+C=10$, $D+E=9$, $B+D=11$, $A+E=10$; plus all-different.

(b) A path: $A - E - D - B - C$.

(c) $A=9, B=3, C=7, D=8, E=1$ — the unique solution; AC-3 alone reduces every domain to a singleton.

Takeaway. Two transferable moves. One: not creating variables for known cells is what kept every constraint binary — a formulation choice, made before any algorithm ran, that decided how hard the problem was. Two: count the variables per constraint before doing anything. Three of these eight lines were secretly unary, and a unary constraint is worth far more than a binary one because it needs no propagation to apply.

Technique: CSP formulation with arity reduction, and AC-3 on a tree-structured constraint graph. Read: Chapter 4, especially the AC-3 section and the structure section on tree-shaped problems.

The instance is tiny and that is deliberate: with three variables and four colours total, you can run both searches exhaustively by hand, so the question is purely about whether you apply each heuristic in the right direction. Pin down the directions before starting:

And note the asymmetry in what counts as success: part (b) does not just take longer, it takes a wrong turn. The question is really "do these heuristics do anything, or are they superstition?"

Choose a variable. Amy 3, Johnny 3, Isha 2. MRV picks Isha.

Choose a value for Isha via LCV. Isha's options are Red and Pink; count what survives elsewhere for each:

LCV wants the largest total, so Isha = Pink. Amy keeps $\{$R, Y, G$\}$, Johnny drops to $\{$R, Y$\}$.

Next variable. Johnny 2, Amy 3. MRV picks Johnny.

Value for Johnny via LCV: $J = $ Red leaves Amy $\{$Y, G$\}$ (2); $J = $ Yellow leaves Amy $\{$R, G$\}$ (2). A tie at 2, broken in rainbow order → Johnny = Red.

Last variable. Amy, domain $\{$Yellow, Green$\}$; rainbow order gives Amy = Yellow.

Isha = Pink,   Johnny = Red,   Amy = Yellow   —   0 backtracks

Straight down the tree with no retraction. Every choice was forced or safe.

Choose a variable. Amy 3, Johnny 3, Isha 2. Maximum remaining values wants the largest; tie between Amy and Johnny, broken by listed order → Amy.

Value for Amy via most constraining:

Most constraining wants the smallest total, so Amy = Red. Now Johnny $\{$Y, P$\}$, Isha $\{$P$\}$.

Next variable. Johnny 2, Isha 1. Maximum remaining values picks Johnny — which is already the mistake: Isha is down to a single option and we are not committing to it.

Value for Johnny via most constraining: $J = $ Yellow leaves Isha $\{$P$\}$ (1); $J = $ Pink leaves Isha $\{\,\}$ (0). Smallest total wins, so Johnny = Pink.

Isha now has an empty domain. Dead end — backtrack. Retract Johnny = Pink and try Johnny = Yellow. Isha $\{$P$\}$ → Isha = Pink. Complete.

Amy = Red,   Johnny = Yellow,   Isha = Pink   —   1 backtrack

And notice how specifically wrong the second heuristic pair was: the "most constraining value" rule deliberately chose the value that emptied Isha's domain. It did not stumble into failure; it optimised for it.

(a) 0 backtracks. (b) 1 backtrack.

One backtrack on a three-variable problem does not sound dramatic, and that is worth saying honestly. The point is the mechanism, which scales:

• MRV assigns the tightest variable first, so a contradiction surfaces at shallow depth. Reversing it leaves the tight variable unassigned while you make choices that can destroy it — which is exactly what happened to Isha.
• LCV tries the value most likely to leave a solution reachable. Reversing it means deliberately picking the value most likely to kill one, and on this instance it picked precisely the fatal one.

On a problem with $n$ variables, a dead end discovered at depth $k$ costs you the whole subtree below it. MRV pushes $k$ down; its mirror pushes $k$ up. The factor is exponential in $n-k$, so one backtrack here is the visible tip of a real effect.

Technique: applying MRV and LCV in the right directions and counting backtracks. Read: Chapter 4, the ordering-heuristics section.

These four are not independent: (d) is built from (b) and (c), and (a) is the thing the other three are used to build. So the right way to hold them is as a chain — entropy measures disorder; conditional entropy measures the disorder left after you look at a feature; mutual information is the difference, i.e. how much looking helped; and a decision tree is what you get by repeatedly choosing the feature that helps most.

A definition answer that states the formula and nothing else is fragile. State the formula, name every symbol, and give the two extremes.

Small worked example — "will it rain today?":

            Cloudy?
           /        \
         no          yes
         |            |
        NO       Temperature
                  /        \
              < 30F       ≥ 30F
                |            |
               YES           NO

Two things to say out loud about this structure, because they come back in part 3.4: each test looks at a single attribute, and the branches out of a node partition the data reaching it. Together those two facts mean a decision tree's decision regions are built from axis-aligned cuts — it can never draw a diagonal boundary in one test.

What it means: the average number of bits needed to communicate a draw of $Y$ under an optimal code; equivalently, how uncertain you are about the outcome. High entropy = less confident.

Extremes, for $Y$ over $k$ values: minimum $H(Y) = 0$ exactly when $Y$ is deterministic (one outcome has probability 1); maximum $H(Y) = \log_2 k$ exactly when $Y$ is uniform. For a binary $Y$ those are 0 and 1 bit.

Practically, for a dataset: split the rows into groups by their value of $X$, compute the label entropy within each group, and average those numbers weighted by group size.

Properties worth being able to state:

• Non-negative: $I(Y;X) \ge 0$ always. Information cannot hurt on average.
• Symmetric: $I(Y;X) = I(X;Y)$, which is why it is called mutual.
• Bounded: $I(Y;X) \le H(Y)$, with equality when $X$ determines $Y$ — a perfect split.
• Zero iff independent: see 3.2(4) below.

Why trees use it: $H(Y)$ is fixed for the data at a node, so maximising $I(Y; X_j)$ over candidate features $j$ is the same as minimising $H(Y \mid X_j)$. That is the shortcut worth using under time pressure: you can skip computing $H(Y)$ entirely and just pick the feature with the smallest weighted post-split entropy.

Technique: precise statement of information-theoretic definitions. Read: Chapter 7 — Entropy & mutual information and Chapter 6 — Decision trees.

Items 1–3 are calibration: they establish the three reference points you should be able to recall instantly, so that in a longer problem you can tell whether an entropy you just computed is plausible. Item 4 is conceptual.

Reference points to memorise: uniform over $k$ outcomes gives $\log_2 k$; deterministic gives 0; and for a binary variable the whole range is $[0, 1]$.

Fair coin. $P(H) = P(T) = \tfrac12$:

$H(Y) = -\tfrac12 \log_2 \tfrac12 - \tfrac12 \log_2 \tfrac12 = -\tfrac12(-1) - \tfrac12(-1) = \mathbf{1} \text{ bit}$

Maximum possible for a binary variable, and it is the definition of the unit: one bit is exactly the uncertainty in one fair coin.

Always-tails coin. $P(H) = 0$, $P(T) = 1$:

$H(Y) = -0\log_2 0 - 1 \log_2 1 = -0 - 0 = \mathbf{0} \text{ bits}$

Both terms vanish, for different reasons: the first by the $0\log_2 0 = 0$ convention, the second because $\log_2 1 = 0$. Zero uncertainty, so no bits are needed to tell you the outcome — you already know it.

Six equally likely outcomes, each with probability $\tfrac16$:

$\displaystyle H(Y) = -\sum_{i=1}^{6} \tfrac16 \log_2 \tfrac16 = -6 \cdot \tfrac16 \log_2 \tfrac16 = -\log_2 \tfrac16 = \log_2 6 \approx \mathbf{2.585} \text{ bits}$

Leave it as $\log_2 6$ unless a decimal is asked for. A useful sanity check: $2 < 2.585 < 3$, matching the fact that 6 outcomes need more than 2 but fewer than 3 bits ($2^2 = 4 < 6 < 8 = 2^3$). This is also the general result — uniform over $k$ gives $\log_2 k$, which is the maximum entropy for a variable with $k$ outcomes.

Exactly when $X$ and $Y$ are independent.

From the definition, $I(Y;X) = 0$ means

$H(Y) - H(Y \mid X) = 0 \quad \Longleftrightarrow \quad H(Y) = H(Y \mid X).$

In words: knowing $X$ leaves your uncertainty about $Y$ completely unchanged. That is what independence is, informationally. (Formally $I(Y;X) = 0 \iff P(X,Y) = P(X)P(Y)$, and the "only if" direction relies on $I \ge 0$ with equality only in that case.)

Three consequences worth having ready:

• In tree-building: a feature with $I(Y; X_j) = 0$ is useless at this node — splitting on it leaves every child with the same label distribution as the parent. If every feature has zero mutual information, no split helps and you should stop and make a leaf.
• $I \ge 0$ always, so zero is the floor, not a mid-range value. There is no such thing as a feature that hurts you on average.
• But a single value can hurt. $H(Y \mid X = x) > H(Y)$ is possible for a particular $x$ — observing one specific outcome can leave you more confused. It is only the average over $x$ that is guaranteed not to. This is exactly why the definition typo in 3.1(d) matters.

Technique: entropy arithmetic and the independence characterisation of mutual information. Read: Chapter 7.

You are running one iteration of the greedy tree-building algorithm, by hand, and then one more. The loop is:

1. Compute $H(Y)$ on the rows at this node.
2. For each remaining attribute, split the rows, compute each group's label entropy, and take the size-weighted average — that is $H(Y \mid X_j)$.
3. $I(Y;X_j) = H(Y) - H(Y \mid X_j)$. Split on the largest.
4. Any branch whose rows all share a label becomes a leaf. Otherwise recurse on just those rows, with that attribute removed.

Two numbers do almost all the work here and are worth memorising: $H$ of a 50/50 split is 1, and $H$ of a 1/3 – 2/3 split is 0.9183. Also $H$ of 2/8 – 6/8 $=$ 1/4 – 3/4 is 0.8113.

Six "yes", two "no", out of 8:

$H(Y) = -\tfrac68 \log_2 \tfrac68 - \tfrac28 \log_2 \tfrac28 = -0.75 \log_2 0.75 - 0.25 \log_2 0.25$

$= 0.75(0.4150) + 0.25(2) = 0.3113 + 0.5 = \mathbf{0.8113} \text{ bits}$

Sanity check: below 1, as it must be for a binary label that is not 50/50, but not far below — 6/8 is only mildly lopsided.

Group the rows:

Weighted average:

$H(Y \mid X_1) = \tfrac38 (0.9183) + \tfrac28 (0) + \tfrac38 (0) = 0.3444$

$I(Y; X_1) = 0.8113 - 0.3444 = \mathbf{0.4669}$

Two of the three branches are already pure, which is why this split scores so well.

Temperature:

$H(Y \mid X_2) = \tfrac38 (0.9183) + \tfrac48 (0.8113) + \tfrac18 (0) = 0.3444 + 0.4056 = 0.7500$

$I(Y; X_2) = 0.8113 - 0.7500 = \mathbf{0.0613}$

Humidity:

$H(Y \mid X_3) = \tfrac48 (1) + \tfrac48 (0) = 0.5000$

$I(Y; X_3) = 0.8113 - 0.5000 = \mathbf{0.3113}$

Interesting: Humidity gives a perfectly pure branch (normal → all yes) and still loses to Outlook, because its other branch is maximally impure (2/2, entropy 1). Purity in one branch is not enough — the weighted average is what is scored.

Split on Outlook. Overcast → leaf YES (rows 2, 8). Rainy → leaf YES (rows 3, 4, 7). Only the sunny branch is mixed, with three rows:

Entropy at the sunny node: 1 yes, 2 no, so $H(Y) = H(\tfrac13) = \mathbf{0.9183}$.

Split on Temperature: hot → {no}, $H = 0$ ($n=1$); mild → {no, yes}, $H = 1$ ($n=2$).

$H(Y \mid X_2) = \tfrac13(0) + \tfrac23(1) = 0.6667 \quad\Rightarrow\quad I(Y;X_2) = 0.9183 - 0.6667 = \mathbf{0.2516}$

Split on Humidity: high → {no, no}, $H = 0$ ($n=2$); normal → {yes}, $H = 0$ ($n=1$).

$H(Y \mid X_3) = \tfrac23(0) + \tfrac13(0) = 0 \quad\Rightarrow\quad I(Y;X_3) = 0.9183 - 0 = \mathbf{0.9183}$

Split on Humidity. The mutual information equals the node's entropy exactly, which is the signature of a perfect split — it removes every remaining bit of uncertainty. Both children are pure, so both are leaves and the tree is finished. Temperature is never used.

Root: $H(Y) = 0.8113$; $I(Y;X_1) = 0.4669$, $I(Y;X_3) = 0.3113$, $I(Y;X_2) = 0.0613$ → split on Outlook.

Sunny node: $H(Y) = 0.9183$; $I(Y;X_3) = 0.9183$, $I(Y;X_2) = 0.2516$ → split on Humidity, which is perfect.

Final tree: see Figure 8. It uses two of the three attributes, has depth 2, and classifies all 8 training rows correctly.

Takeaways.

• Weight by group size. Humidity's "normal" branch was perfectly pure and Humidity still lost at the root. Purity in one branch is not a score.
• $I = H(\text{node})$ means a perfect split, and $I = 0$ means a useless one. Those two landmarks let you check an answer instantly.
• The shortcut: $H(Y)$ is the same for every candidate attribute at a node, so you can rank attributes by $H(Y \mid X_j)$ alone, smallest first, and never compute $H(Y)$ at all. Under exam time pressure this halves the arithmetic. Compute $H(Y)$ only if the question asks for $I$ as a number.
• Greedy is not optimal. Nothing here proves this is the smallest tree that fits the data — the algorithm picks the locally best split at each node and never reconsiders. It just happens to find a tidy tree on this dataset.

Technique: hand-running greedy decision-tree induction with information gain. Read: Chapter 6 for the algorithm and Chapter 7 for the entropy arithmetic.

This is a question about the hypothesis class, not about any particular algorithm. One fact decides everything:

So the question becomes: can this dataset be carved up by axis-aligned boxes, and how many do you need? "Zero error" is always achievable if no two identical points carry different labels — worst case you isolate each point in its own box. The real question is how many cuts, and that is what distinguishes the two datasets.

The classes sit in diagonal quadrants: circles in bottom-left and top-right, crosses in bottom-right and top-left. That is an XOR pattern, and it is exactly what axis-aligned cuts are good at — even though a single straight line cannot do it at all.

The tree:

          x1 < 3 ?
         /         \
       yes          no
        |            |
    x2 < 3 ?     x2 < 3 ?
    /     \       /     \
  yes     no    yes     no
   |       |     |       |
circle  cross  cross  circle

Depth 2, two distinct thresholds, four leaves, zero training error on all 12 points — verified by evaluating this tree on every point in Figure 9's table.

Worth noting explicitly: no single linear boundary gets zero error here. Logistic regression on the raw features would fail on this dataset while a depth-2 tree nails it. This is the standard demonstration that "linear" and "simple" are not the same thing, and it is the reason feature engineering exists for linear models.

Here one straight cut would do the whole job — the line $x_2 = x_1 + 0.6$ separates the classes perfectly. But it is diagonal, and a tree cannot test $x_2 - x_1 < 0.6$ in a single node. So it has to approximate the diagonal with a staircase: slice the plane into vertical strips, and inside each strip put a horizontal cut at roughly the right height.

A tree that achieves zero error on the 12 points, with vertical cuts at $x_1 = 2, 3, 4, 5$ and one horizontal threshold per strip:

Depth 3, nine internal nodes, zero training error on all 12 points — again verified point by point.

The honest reading of this result: the tree fits the data perfectly and has not learned the rule. It has learned five unrelated horizontal thresholds that happen to bracket the twelve points it saw. Watch it fail on fresh points inside the strip $2 \le x_1 < 3$, where its rule is "circle if $x_2 > 2.2$":

Every point in that strip with $2.2 < x_2 < x_1 + 0.6$ is misclassified, and that is a triangular wedge of real area. The staircase's corners are exactly where it generalises badly, and the wedges live in every strip.

And the approximation only gets better by getting finer: each extra step is one more cut, one more level of depth, and more opportunity to overfit. That is the trade-off problem 3.5 is about.

A: a depth-2 tree with two thresholds ($x_1 = 3$, $x_2 = 3$) gives zero error. A single linear boundary cannot.

B: a 5-step staircase gives zero error, but needs 9 internal nodes to approximate a boundary that one diagonal line would capture exactly.

Technique: reasoning about a hypothesis class's decision-boundary geometry, and distinguishing "fits the training data" from "learned the rule". Read: Chapter 6 for tree boundaries, Chapter 11 for linear ones, and Chapter 10 for how a feature transform turns dataset B into an easy problem for a linear model (add the feature $x_2 - x_1$ and one threshold does it).

All five are the bias–variance story told through one hyperparameter. The frame that answers all of them at once:

max_depth is a capacity knob. Turning it up lets the tree carve the feature space into more and smaller boxes. Too few boxes and the tree cannot express the pattern (underfitting, high bias). Too many and each box is shaped by a handful of points, including their noise (overfitting, high variance). Training error falls monotonically as depth rises; validation error falls, bottoms out, then rises. You tune on validation error, never on training error.

(1) Best max_depth: somewhere around 2 to 8, varying with the train/validation split and the implementation. The criterion is the one that matters: the depth minimising validation error, not training error, which keeps improving all the way down and so can never select a depth.

Iris being nearly separable on two of its four features, depth 2–3 already does well, and anything deeper buys very little. When several depths tie on validation error, prefer the shallowest — fewer parameters, better expected generalisation, and easier to explain.

(2) Why the error is large at very small depth: with max_depth $= 1$ the tree makes a single split, so it has exactly 2 leaves and can output at most 2 distinct labels. On a 3-class problem, one class is therefore guaranteed to be wrong — a structural ceiling, independent of data or tuning. More generally, a shallow tree's leaves each hold a large and mixed set of rows; the leaf predicts the majority and is wrong on the rest. The leaf's label entropy is still high, which is exactly the diagnostic: a leaf with high entropy is a leaf that should have been split. This is underfitting: insufficient capacity to represent the structure that is really there.

Note that the depth-1 argument is a nice crisp thing to write in an exam: depth $d$ gives at most $2^d$ leaves, hence at most $2^d$ distinct predictions, so with $K$ classes you need $d \ge \log_2 K$ before zero error is even possible.

(3) Relation to overfitting. Deeper trees overfit. The mechanism, concretely: as depth grows, the algorithm keeps splitting until leaves contain one or two training points, and it will happily split on a feature that separates two points by accident. That split is memorisation, not pattern. Result: training error → 0 while validation error rises, because the fine structure was noise and the noise does not repeat in new data.

The honest refinement: depth is a bound on capacity, not capacity itself. If the data is cleanly separable with few splits, the tree may stop early regardless of a large max_depth, and raising the cap further changes nothing. That is why the validation curve usually flattens at the right rather than shooting up — and why the answer to (1) is a range.

(5) Most complex boundaries. At the largest depths. Each additional level adds more axis-aligned cuts, so the decision regions become more numerous and smaller and the boundary becomes a finer staircase — precisely the shape in Figure 9's right panel, with more and smaller steps. Maximum depth gives maximum boundary complexity, and past the validation minimum that extra complexity is tracking noise.

A sharper version of the same claim: boundary complexity is governed by the number of leaves, which is at most $2^d$. Depth bounds complexity exponentially, which is why a modest change in max_depth can change the picture so much.

Because Iris has 4 features (sepal length, sepal width, petal length, petal width), so its feature space is $\mathbb{R}^4$ and the decision boundary is a 3-dimensional surface in it. A sheet of paper shows 2 dimensions.

Lecture's pictures were drawn after picking 2 of the 4 features and discarding the rest, which makes the plot honest about that 2-feature model and misleading about the 4-feature one.

The standard workarounds, worth naming:

• Select 2 features and train on only those. Honest, but a different model.
• Project to 2 dimensions (PCA, say) and plot. Shows the data, but the boundary becomes approximate, since a projected boundary is not generally a boundary.
• Plot a 2-D slice: vary two features and hold the other two at their means. Exact, but only along that slice.
• Draw the tree itself instead of the boundary. For a tree this is the best option: the tree is a complete, exact and readable description of the boundary in any number of dimensions, which is not true of most model classes.

Technique: hyperparameter tuning as capacity control; reading a train/validation error curve; the limits of visualisation above 2 features. Read: Chapter 12 — Regularization & cross-validation for the tuning procedure, and Chapter 6 for depth as a capacity bound.

One idea, four packagings, distinguished entirely by what is a scalar and what is a vector on each side:

That last ambiguity is precisely what (d) is about, and it is the reason this course states a layout convention on every question that needs one.

With $f(x_1, x_2) = x_1^3 + e^{x_2} x_1$:

$\dfrac{\partial f}{\partial x_1} = \dfrac{\partial}{\partial x_1}\!\left(x_1^3\right) + \dfrac{\partial}{\partial x_1}\!\left(e^{x_2} x_1\right) = 3x_1^2 + e^{x_2}$

In the second term, $e^{x_2}$ is a constant multiplier as far as $x_1$ is concerned, so it comes along untouched. And the other partial:

$\dfrac{\partial f}{\partial x_2} = 0 + x_1 e^{x_2} = x_1 e^{x_2}$

Here $x_1^3$ has no $x_2$ in it, so it differentiates to 0, and $x_1$ is the constant multiplier.

For our $f$, with $M = 2$:

$\nabla f(\mathbf{x}) = \begin{bmatrix} 3x_1^2 + e^{x_2} \\ x_1 e^{x_2} \end{bmatrix}$

Notation note the handout flags, and it matters: the $\mathbf{x}$ in $\nabla f(\mathbf{x})$ is bold — a vector, not a scalar. Throughout this course bold lowercase means a vector, capital means a matrix, and plain lowercase means a scalar. Getting that wrong turns a correct derivation into an incoherent one, and it is the first thing a grader checks.

The gradient is the special case $N = 1$: a single column. The numerator layout is this matrix transposed, $N \times M$ — see Step 5.

The two layouts contain identical information and differ by a transpose. The course states which one to use; you must be able to work in either.

Applying it, with $\mathbf{y} \in \mathbb{R}^N$, $\mathbf{v} \in \mathbb{R}^{N \times 1}$, $A \in \mathbb{R}^{M \times N}$, $y$ a scalar:

Check the last row with the rule. $A\mathbf{v} \in \mathbb{R}^{M}$ is the numerator, $\mathbf{v} \in \mathbb{R}^{N}$ the denominator. Numerator layout wants $M$ rows, and $A$ is $M \times N$ — correct. Denominator layout wants $N$ rows, and $A^\top$ is $N \times M$ — correct. The rule never needs memorising past that.

Technique: derivative shapes and layout conventions. Read: Chapter 8 — Linear regression, which sets up this notation, and Chapter 9, which uses it.

Do not reach for an identity. The whole point of this problem is the technique you fall back on when you do not recognise the expression: expand to scalars, differentiate component by component, then re-stack into a vector. That technique always works and it is what the proof in 4.4 does at larger scale.

Shape check before starting: $J$ is a scalar function of a $2 \times 1$ vector, so $\nabla J(\mathbf{z})$ must be $2 \times 1$.

By definition $\lVert \mathbf{a} \rVert_2^2 = \sum_i a_i^2$, so with $\mathbf{a} = \mathbf{y} - \mathbf{z}$:

$J(\mathbf{z}) = \left\lVert \begin{bmatrix} y_1 - z_1 \\ y_2 - z_2\end{bmatrix} \right\rVert_2^2 = (y_1 - z_1)^2 + (y_2 - z_2)^2$

Now it is an ordinary two-variable calculus problem with no vectors in sight. Note the squared norm has no square root, which is exactly why this is pleasant to differentiate — squared loss is used partly for this reason.

With respect to $z_1$, the second term is constant:

$\dfrac{\partial J}{\partial z_1} = \dfrac{\partial}{\partial z_1}(y_1 - z_1)^2 = 2(y_1 - z_1) \cdot \dfrac{\partial (y_1 - z_1)}{\partial z_1} = 2(y_1 - z_1)(-1) = -2(y_1 - z_1)$

The chain rule supplies the inner derivative $-1$, and that minus sign is the single most commonly dropped thing in this problem. Identically for $z_2$:

$\dfrac{\partial J}{\partial z_2} = -2(y_2 - z_2)$

Stack the partials into a column:

$\nabla J(\mathbf{z}) = \begin{bmatrix} -2(y_1 - z_1) \\ -2(y_2 - z_2)\end{bmatrix} = -2\begin{bmatrix} y_1 - z_1 \\ y_2 - z_2 \end{bmatrix} = \boxed{-2(\mathbf{y} - \mathbf{z})}$

Shape check: $\mathbf{y} - \mathbf{z}$ is $2 \times 1$, scaled by $-2$, still $2 \times 1$. Matches the requirement from Step 1. ✓

Verification: a central-difference numerical gradient of $J$ at $\mathbf{y} = (2, -1)$, $\mathbf{z} = (0.5, 0.4)$ gives $(-3.0,\ 2.8)$, and $-2(\mathbf{y} - \mathbf{z}) = -2(1.5,\ -1.4) = (-3.0,\ 2.8)$. Agreed to 6 decimal places.

Takeaways. The result generalises immediately to any dimension: $\nabla_{\mathbf{z}} \lVert \mathbf{y} - \mathbf{z}\rVert_2^2 = -2(\mathbf{y} - \mathbf{z})$. Two things to carry:

• It points away from $\mathbf{y}$. The negative gradient is $+2(\mathbf{y} - \mathbf{z})$, which points from $\mathbf{z}$ straight at $\mathbf{y}$. So gradient descent on squared distance walks you directly towards the target — a useful geometric check on any gradient you derive.
• Setting it to zero gives $\mathbf{z} = \mathbf{y}$, the unique minimiser, which is obviously right and confirms no sign error.

Technique: expand-differentiate-restack, plus the chain-rule sign. This is exactly the gradient of the squared-error loss in Chapter 8, where $\mathbf{z} = X\boldsymbol{\theta}$.

The tempting answer is $\dfrac{\partial \mathbf{y}}{\partial \mathbf{x}} = 2\mathbf{x}$, by analogy with the scalar fact $\frac{d}{dx} x^2 = 2x$.

Shape check kills it instantly. This is a map $\mathbb{R}^3 \to \mathbb{R}^3$, so its derivative is a Jacobian: $3 \times 3$ in either layout. But $2\mathbf{x}$ is $3 \times 1$. Nine numbers are required and three were offered, so the answer cannot be right — no calculus needed to know that.

This is the payoff of the shape habit. You caught a wrong answer without differentiating anything.

Numerator layout: rows indexed by the numerator $\mathbf{y}$, columns by the denominator $\mathbf{x}$. So entry $(i,j)$ is $\partial y_i / \partial x_j$:

$\dfrac{\partial \mathbf{y}}{\partial \mathbf{x}} = \begin{bmatrix} \frac{\partial y_1}{\partial x_1} & \frac{\partial y_1}{\partial x_2} & \frac{\partial y_1}{\partial x_3} \\[2pt] \frac{\partial y_2}{\partial x_1} & \frac{\partial y_2}{\partial x_2} & \frac{\partial y_2}{\partial x_3} \\[2pt] \frac{\partial y_3}{\partial x_1} & \frac{\partial y_3}{\partial x_2} & \frac{\partial y_3}{\partial x_3}\end{bmatrix}$

Now evaluate. Since $y_i = x_i^2$ depends on $x_i$ only:

• On the diagonal: $\partial y_i / \partial x_i = 2x_i$.
• Off the diagonal: $\partial y_i / \partial x_j = 0$ for $i \neq j$, because $y_i$ contains no $x_j$ at all.

$\dfrac{\partial \mathbf{y}}{\partial \mathbf{x}} = \begin{bmatrix} 2x_1 & 0 & 0 \\ 0 & 2x_2 & 0 \\ 0 & 0 & 2x_3\end{bmatrix} = 2\,\mathrm{diag}(\mathbf{x})$

$\boxed{\dfrac{\partial \mathbf{y}}{\partial \mathbf{x}} = 2\,\mathrm{diag}(x_1, x_2, x_3) \in \mathbb{R}^{3\times3}}$

In this case the two layouts agree, because the matrix is symmetric (diagonal). That is a coincidence of this problem, not a general fact — do not let it make you careless about layout elsewhere.

Takeaways.

• Diagonal Jacobian $\iff$ elementwise function. The zero off-diagonal entries are the statement "output $i$ depends only on input $i$". Whenever you see an elementwise operation, expect a diagonal Jacobian, and vice versa. This is why elementwise activation functions are cheap to backpropagate through — a diagonal matrix product is just a vectorised multiply.
• "$2\mathbf{x}$" was not merely the wrong shape, it was the wrong kind of object. The scalar intuition does not transfer; what transfers is the entry-by-entry construction.
• Shape-check first. It is faster than differentiating and it catches the most common class of error.

Technique: Jacobian construction and layout discipline. Read: Chapter 9 — Optimization.

A proof by direct computation. The strategy that makes it painless is the hint's third line: work from both ends. Expand the left side down to scalars; expand the right side down to scalars; show they are the same two expressions. Marching blindly from the left and hoping to recognise the answer is how people get stuck.

Shape check first. $\mathbf{v}^\top A \mathbf{v}$ is $(1\times2)(2\times2)(2\times1) = 1 \times 1$ — a scalar. Differentiating a scalar by a $2\times1$ vector in denominator layout gives a $2 \times 1$ column. On the right, $(A^\top + A)$ is $2\times2$ and $\mathbf{v}$ is $2 \times 1$, so the product is $2 \times 1$. ✓ Both sides are columns of length 2, so the claim is at least coherent.

Write everything out:

$\mathbf{v} = \begin{bmatrix} v_1 \\ v_2\end{bmatrix}, \qquad A = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22}\end{bmatrix}, \qquad A^\top = \begin{bmatrix} A_{11} & A_{21} \\ A_{12} & A_{22}\end{bmatrix}$

First $\mathbf{v}^\top A$, a $1 \times 2$ row:

$\mathbf{v}^\top A = \begin{bmatrix} v_1 & v_2\end{bmatrix}\begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22}\end{bmatrix} = \begin{bmatrix} A_{11}v_1 + A_{21}v_2 & \;\; A_{12}v_1 + A_{22}v_2\end{bmatrix}$

Then multiply by $\mathbf{v}$ on the right:

$\mathbf{v}^\top A \mathbf{v} = \begin{bmatrix} A_{11}v_1 + A_{21}v_2 & A_{12}v_1 + A_{22}v_2\end{bmatrix}\begin{bmatrix} v_1 \\ v_2\end{bmatrix}$

$= A_{11}v_1^2 + A_{21}v_1 v_2 + A_{12}v_1v_2 + A_{22}v_2^2$

A scalar quadratic in $v_1, v_2$. Note that $A_{12}$ and $A_{21}$ appear only through the cross term, and only as the sum $A_{12} + A_{21}$. That observation is already the whole content of the theorem; the rest is bookkeeping.

Differentiate the polynomial with respect to $v_1$, treating $v_2$ as constant. The $A_{22}v_2^2$ term vanishes:

$\dfrac{\partial}{\partial v_1}\left(\mathbf{v}^\top A \mathbf{v}\right) = 2A_{11}v_1 + A_{21}v_2 + A_{12}v_2$

And with respect to $v_2$; now $A_{11}v_1^2$ vanishes:

$\dfrac{\partial}{\partial v_2}\left(\mathbf{v}^\top A \mathbf{v}\right) = A_{21}v_1 + A_{12}v_1 + 2A_{22}v_2$

Stack into a column, which is what denominator layout asks for:

$\dfrac{\partial}{\partial \mathbf{v}}\mathbf{v}^\top A \mathbf{v} = \begin{bmatrix} 2A_{11}v_1 + A_{21}v_2 + A_{12}v_2 \\ A_{21}v_1 + A_{12}v_1 + 2A_{22}v_2\end{bmatrix}$   (LHS)

The factor of 2 on the diagonal terms comes from the square; the cross terms contribute $A_{12} + A_{21}$ once each. Hold that thought.

Add the two matrices entrywise:

$A^\top + A = \begin{bmatrix} A_{11} & A_{21} \\ A_{12} & A_{22}\end{bmatrix} + \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22}\end{bmatrix} = \begin{bmatrix} 2A_{11} & A_{12} + A_{21} \\ A_{12} + A_{21} & 2A_{22}\end{bmatrix}$

This matrix is symmetric, which is worth noticing: $A^\top + A$ is always symmetric, for any $A$. Now multiply by $\mathbf{v}$:

$(A^\top + A)\mathbf{v} = \begin{bmatrix} 2A_{11} & A_{12}+A_{21} \\ A_{12}+A_{21} & 2A_{22}\end{bmatrix}\begin{bmatrix} v_1 \\ v_2\end{bmatrix} = \begin{bmatrix} 2A_{11}v_1 + (A_{12} + A_{21})v_2 \\ (A_{12}+A_{21})v_1 + 2A_{22}v_2\end{bmatrix}$   (RHS)

Compare (LHS) and (RHS) entry by entry:

Identical after factoring. ■

The handout asks whether the result holds in general. It does, and the index-notation proof is three lines once you have seen the $2\times2$ case.

Write the quadratic form as a double sum:

$\mathbf{v}^\top A \mathbf{v} = \displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n} v_i A_{ij} v_j$

Differentiate with respect to $v_k$. The variable $v_k$ appears in a term $v_i A_{ij} v_j$ exactly when $i = k$ or $j = k$, so split the sum into three disjoint groups — terms with $i=k, j \neq k$; terms with $j = k, i \neq k$; and the single term $i = j = k$:

$\dfrac{\partial}{\partial v_k}\sum_{i,j} v_i A_{ij}v_j = \underbrace{\sum_{j \neq k} A_{kj}v_j}_{i=k} \; + \; \underbrace{\sum_{i\neq k} v_i A_{ik}}_{j=k} \; + \; \underbrace{2A_{kk}v_k}_{i=j=k}$

The last term carries a 2 because $v_k A_{kk} v_k = A_{kk}v_k^2$. Now fold one $A_{kk}v_k$ into each of the first two sums, which restores their full ranges:

$= \sum_{j=1}^{n} A_{kj}v_j + \sum_{i=1}^{n} A_{ik}v_i = (A\mathbf{v})_k + (A^\top \mathbf{v})_k = \left((A + A^\top)\mathbf{v}\right)_k$

Since this holds for every $k$, the full column is $(A^\top + A)\mathbf{v}$. ■

Recognising the two sums is the only step that needs care: $\sum_j A_{kj}v_j$ is the $k$-th entry of $A\mathbf{v}$ (row $k$ of $A$ dotted with $\mathbf{v}$), while $\sum_i A_{ik}v_i$ is the $k$-th entry of $A^\top \mathbf{v}$ (column $k$ of $A$ dotted with $\mathbf{v}$).

Numerical verification. With $A = \begin{bmatrix} 2 & -3 \\ 5 & 1\end{bmatrix}$ and $\mathbf{v} = (1.3, -0.7)$, a central-difference gradient gives $(3.8,\ 1.2)$ and $(A^\top + A)\mathbf{v}$ gives $(3.8,\ 1.2)$. A random $4 \times 4$ instance agrees to within $4 \times 10^{-10}$, which is numerical-differentiation noise.

$\boxed{\dfrac{\partial}{\partial \mathbf{v}}\mathbf{v}^\top A \mathbf{v} = (A^\top + A)\mathbf{v}} \qquad \text{for any } A \in \mathbb{R}^{n\times n},\ \mathbf{v} \in \mathbb{R}^n$

Takeaways.

• Work from both ends. Expanding the target alongside the source is what makes this proof mechanical instead of a guessing game.
• Only $A_{12} + A_{21}$ ever appears. That is why the answer involves $A + A^\top$: a quadratic form cannot distinguish $A$ from its symmetric part, so neither can its derivative.
• Shape-check at the start. Confirming both sides are $n \times 1$ before computing anything is thirty seconds that protects the whole derivation.

Technique: proving a matrix-calculus identity by expansion, in both index and explicit form. Read: Chapter 8, where this identity produces the normal equations — which is exactly Problem 4.4.

This is the payoff problem: the two identities you just proved are exactly the two you need, and nothing else is required. Identify which identity applies to which term before differentiating:

Shapes, with $X \in \mathbb{R}^{N \times M}$, $\mathbf{y} \in \mathbb{R}^{N\times1}$, $\boldsymbol{\theta} \in \mathbb{R}^{M \times 1}$: $X^\top \mathbf{y}$ is $M \times 1$, $X^\top X$ is $M \times M$, and $\nabla J$ must be $M \times 1$. Everything below should stay $M \times 1$.

$\nabla J(\boldsymbol{\theta}) = \dfrac{\partial}{\partial \boldsymbol{\theta}}\dfrac{1}{N}\left(\mathbf{y}^\top\mathbf{y} - 2\boldsymbol{\theta}^\top X^\top \mathbf{y} + \boldsymbol{\theta}^\top X^\top X \boldsymbol{\theta}\right)$

Term 1: $\mathbf{y}^\top \mathbf{y}$ contains no $\boldsymbol{\theta}$, so its derivative is the zero vector.

Term 2: apply $\partial\,\mathbf{v}^\top\mathbf{u}/\partial\mathbf{v} = \mathbf{u}$ with $\mathbf{v} = \boldsymbol{\theta}$ and $\mathbf{u} = X^\top \mathbf{y}$, keeping the $-2$:

$\dfrac{\partial}{\partial\boldsymbol{\theta}}\left(-2\boldsymbol{\theta}^\top X^\top \mathbf{y}\right) = -2X^\top \mathbf{y}$

Term 3: apply $(A^\top + A)\mathbf{v}$ with $A = X^\top X$:

$\dfrac{\partial}{\partial\boldsymbol{\theta}}\left(\boldsymbol{\theta}^\top X^\top X \boldsymbol{\theta}\right) = \left((X^\top X)^\top + X^\top X\right)\boldsymbol{\theta}$

Now simplify using the fact that $X^\top X$ is symmetric: $(X^\top X)^\top = X^\top (X^\top)^\top = X^\top X$. So the bracket is $2X^\top X$ and the term is $2X^\top X \boldsymbol{\theta}$.

Assembling:

$\nabla J(\boldsymbol{\theta}) = \dfrac{1}{N}\left(\mathbf{0} - 2X^\top \mathbf{y} + 2X^\top X\boldsymbol{\theta}\right) = \boxed{\dfrac{2}{N}\left(X^\top X\boldsymbol{\theta} - X^\top \mathbf{y}\right)}$

Shape check: $X^\top X \boldsymbol{\theta}$ is $(M\times M)(M\times1) = M \times 1$; $X^\top \mathbf{y}$ is $M \times 1$. Their difference is $M \times 1$. ✓

$J$ is convex in $\boldsymbol{\theta}$ (a positive multiple of a squared norm of an affine function), so a stationary point is a global minimum. Set $\nabla J = \mathbf{0}$:

$\dfrac{2}{N}\left(X^\top X \boldsymbol{\theta} - X^\top \mathbf{y}\right) = \mathbf{0}$

The scalar $2/N$ is non-zero, so divide it out:

$X^\top X \boldsymbol{\theta} - X^\top \mathbf{y} = \mathbf{0} \qquad \Longrightarrow \qquad X^\top X \boldsymbol{\theta} = X^\top \mathbf{y}$

These are the normal equations. Left-multiply by $(X^\top X)^{-1}$, assuming it exists:

$\boxed{\boldsymbol{\theta} = \left(X^\top X\right)^{-1} X^\top \mathbf{y}}$

Shape check: $(M\times M)(M \times N)(N\times1) = M\times1$. ✓

Numerical verification. On a 4-point dataset with $X = [\mathbf{1}, (1,2,3,4)]$ and $\mathbf{y} = (2,\ 2.9,\ 4.2,\ 4.9)$, the closed form gives $\boldsymbol{\theta} = (1.0,\ 1.0)$ exactly, and the numerical gradient of $J$ at that $\boldsymbol{\theta}$ is zero to 10 decimal places — confirming it is a stationary point, as the derivation claims.

(1) $\nabla J(\boldsymbol{\theta}) = \frac{2}{N}\left(X^\top X \boldsymbol{\theta} - X^\top \mathbf{y}\right)$.   (2) $\boldsymbol{\theta} = (X^\top X)^{-1}X^\top \mathbf{y}$.

Takeaways.

• This is why Problem 4.3 exists. The entire vector-calculus recitation is scaffolding for this one derivation, and the derivation is the reason linear regression has a closed form at all — something almost no other model in this course has. Logistic regression, by contrast, has no closed form, which is why Chapter 9 exists.
• Symmetry of $X^\top X$ does real work. Without it you would be stuck with $\left((X^\top X)^\top + X^\top X\right)\boldsymbol{\theta}$ and could not simplify. Expect to be asked to justify that step.
• Shape-check every line. Four shape checks appear above and each one would have caught a transposition error.

Technique: applying matrix-calculus identities to derive a closed-form estimator. Read: Chapter 8 — Linear regression for the full treatment including the invertibility conditions.

These six are one idea stretched in two directions. Hold the structure, not six separate cards:

linear score $\to$ squash to a probability $\to$ generalise the squash to $K$ classes $\to$ score it with cross-entropy

Throughout, assume $\mathbf{x}$ has been augmented with a leading 1 so that $\boldsymbol{\theta}^\top \mathbf{x}$ includes a bias term and no separate intercept is needed. Also throughout: a superscript $(i)$ indexes the example, not a power. $\mathbf{x}^{(i)}$ is the $i$-th training input.

The derivative is worth knowing by heart: $g'(z) = g(z)\left(1 - g(z)\right)$. It is maximal ($= \tfrac14$) at $z = 0$ and vanishes as $|z| \to \infty$, which is the saturation that makes very confident logistic units learn slowly.

So logistic regression is "linear regression's score, pushed through a sigmoid, and read as $P(Y=1)$". The complement is automatic:

$P(Y = 0 \mid \mathbf{x};\boldsymbol\theta) = 1 - \dfrac{1}{1+e^{-z}} = \dfrac{e^{-z}}{1+e^{-z}}, \qquad z = \boldsymbol\theta^\top\mathbf{x}$

Why bother: class labels are nominal, and the integers $1,2,3$ carry an arithmetic the classes do not have. Encoding class 3 as the number 3 implies it is "between" 2 and 4 and three times class 1 — nonsense for chocolate, vanilla, strawberry. One-hot removes that false structure, and it also makes the cross-entropy sum in (f) collapse to a single term.

One-vs-all. Train $K$ independent binary logistic models. For each $k$, relabel the data so class $k$ is positive and everything else is negative, fit $\boldsymbol\theta_k$, and obtain $P(Y_k = 1 \mid \mathbf{x}; \boldsymbol\theta_k)$. Predict by $\hat{y} = \arg\max_k P(Y_k = 1 \mid \mathbf{x};\boldsymbol\theta_k)$.

Two weaknesses, both worth being able to name:

• It ignores the relationship between classes — each model is fit blind to the others.
• It loses the probabilistic interpretation. The $K$ outputs are probabilities from $K$ unrelated models and in general do not sum to 1, so the argmax is a vote, not a posterior.

Softmax (multinomial logistic regression). One model, $K$ parameter vectors, tied together. Define $K$ linear scores $z_k = \boldsymbol\theta_k^\top \mathbf{x}$ and normalise them jointly:

$g_{\text{softmax}}(\mathbf{z}) = \dfrac{1}{\sum_{k=1}^{K} e^{z_k}}\begin{bmatrix} e^{z_1} \\ e^{z_2} \\ \vdots \\ e^{z_K}\end{bmatrix}$

Every entry is in $(0,1)$ and they sum to exactly 1, so the output is a probability distribution. Stacking the parameter vectors as rows of a matrix:

$\Theta = \begin{bmatrix} -\!\!-\ \boldsymbol\theta_1^\top\ -\!\!- \\ -\!\!-\ \boldsymbol\theta_2^\top\ -\!\!- \\ \vdots \\ -\!\!-\ \boldsymbol\theta_K^\top\ -\!\!-\end{bmatrix}, \qquad \mathbf{z} = \Theta \mathbf{x}, \qquad \hat{\mathbf{y}} = h_\Theta(\mathbf{x}) = g_{\text{softmax}}(\Theta\mathbf{x})$

with $\hat{y}_k = P(Y_k = 1 \mid \mathbf{x}; \Theta)$. Shapes: $\Theta$ is $K \times M$, $\mathbf{x}$ is $M \times 1$, so $\mathbf{z}$ and $\hat{\mathbf{y}}$ are $K \times 1$.

It measures how far the predicted distribution is from the true one. The key simplification, which is what makes it cheap:

Properties: $J \ge 0$; $J \to 0$ as the model gets the right class probability $\to 1$; and $J \to \infty$ if the model assigns probability $\to 0$ to a correct class. That last property is the point — cross-entropy punishes confident wrongness unboundedly, where accuracy would merely count it as one error.

Technique: the definitional chain from linear score to multiclass probabilistic prediction. Read: Chapter 11 — Logistic regression, with Chapter 8 for the starting point.

Part 3 is secretly the important one: it is building, from arithmetic, the fact that $\boldsymbol\theta^\top\mathbf{x} = 0$ is the decision boundary. Everything else in part 3 is there so that the boundary falls out of numbers rather than being asserted.

Note that part 3 asks you to construct an $\mathbf{x}$, so there are many right answers. Pick the easiest ones.

When to use logistic: whenever the label is binary (or categorical, via softmax). Three concrete reasons linear regression is the wrong tool for a 0/1 label:

• It predicts values outside $[0,1]$, which cannot be probabilities.
• Squared error on a 0/1 target penalises confidently-correct predictions that overshoot, which is incoherent.
• It is badly destabilised by outliers in $\mathbf{x}$, because a far-away point drags the whole fitted line and so moves the implied threshold.

The honest symmetry: both are linear in the parameters and both have linear decision structure. Logistic regression's boundary is a hyperplane, just like linear regression's fit — the sigmoid changes the output, not the geometry of the boundary.

A Bernoulli distribution over the binary class variable $Y$, conditioned on $\mathbf{x}$:

$P(Y = 1 \mid \mathbf{x}) = \dfrac{1}{1+e^{-z}}, \qquad P(Y = 0 \mid \mathbf{x}) = 1 - \dfrac{1}{1+e^{-z}} = \dfrac{e^{-z}}{1+e^{-z}}$

with $z = \boldsymbol\theta^\top \mathbf{x}$. The two probabilities sum to 1 by construction, and the open interval $(0,1)$ is exactly right: a logistic model is never absolutely certain, which matters because $\log 0$ in the cross-entropy would be infinite.

A neat identity worth knowing: dividing the two gives $\dfrac{P(Y=1\mid\mathbf{x})}{P(Y=0\mid\mathbf{x})} = e^{z}$, so $\log \dfrac{P(Y=1\mid\mathbf{x})}{P(Y=0\mid\mathbf{x})} = \boldsymbol\theta^\top\mathbf{x}$. The model is linear in the log-odds. That is the cleanest one-line characterisation of logistic regression there is.

(a) Want $\boldsymbol\theta^\top\mathbf{x} > 0$. The simplest choice is $\mathbf{x} = (1, 1, 1)^\top$:

$\boldsymbol\theta^\top\mathbf{x} = 1(1) + 4(1) + 3(1) = 8 > 0$

$g(8) = \dfrac{1}{1+e^{-8}} = \mathbf{0.99966}$

Very close to 1 — the model is confidently predicting class 1.

(b) Want $\boldsymbol\theta^\top\mathbf{x} = 0$. Solve $x_1 + 4x_2 + 3x_3 = 0$; one easy solution is $\mathbf{x} = (7, -1, -1)^\top$:

$\boldsymbol\theta^\top\mathbf{x} = 7 - 4 - 3 = 0, \qquad g(0) = \dfrac{1}{1+e^{0}} = \dfrac{1}{2} = \mathbf{0.5}$

The general relationship. $g$ is strictly increasing with $g(0) = \tfrac12$, so the sign of $z$ determines which side of a half you land on:

And since $|z|$ controls how far from 0.5 you land, $|z|$ is the model's confidence: $g(0) = 0.5$, $g(3) \approx 0.953$, $g(8) \approx 0.99966$. Geometrically, $|z|$ is proportional to the distance from $\mathbf{x}$ to the decision hyperplane.

Technique: connecting the sigmoid's shape to the geometry of the decision boundary. Read: Chapter 11, and Chapter 10 for how to get a non-linear boundary out of a linear model by transforming $\mathbf{x}$.

Three mechanical steps and one piece of bookkeeping that catches people out: the augmented input. $\Theta$ is $3 \times 3$, so $\mathbf{x}$ must be $3 \times 1$ — but the data gives only two features. The first column of $\Theta$ is the bias column, so

$\mathbf{x}^{(i)} = \begin{bmatrix} 1 \\ \text{mood} \\ \text{hunger}\end{bmatrix}$

and because the bias column of $\Theta$ is all zeros, that leading 1 contributes nothing numerically here — but the shapes do not work without it. Shape-check before computing.

Then, per sample: $\mathbf{z}^{(i)} = \Theta\mathbf{x}^{(i)}$, $\hat{\mathbf{y}}^{(i)} = g_{\text{softmax}}(\mathbf{z}^{(i)})$, and the loss uses only the entry of $\hat{\mathbf{y}}$ at the true class.

Row $k$ of $\Theta$ dotted with $\mathbf{x}$. For sample 1, $\mathbf{x} = (1, 1, 1)^\top$:

$z_1 = 0(1) + 3.8(1) + 3.9(1) = 7.7, \quad z_2 = 0 + 4.6 + 3.8 = 8.4, \quad z_3 = 0 + 5.4 + 3.1 = 8.5$

All five, computed the same way:

Check one by hand: sample 2, $z_2 = 0(1) + 4.6(4) + 3.8(5) = 18.4 + 19 = 37.4$. ✓

Applying $\hat{y}_k = e^{z_k}/\sum_l e^{z_l}$ naively to sample 5 means computing $e^{42.5}$, which is about $2.9 \times 10^{18}$. That overflows in low precision and is unpleasant by hand. The fix:

Sample 5: subtract 42.5 to get $(-4.0, -0.5, 0)$, then $e^{-4} = 0.0183$, $e^{-0.5} = 0.6065$, $e^{0} = 1$, summing to 1.6248. Dividing: $(0.0113,\ 0.3733,\ 0.6154)$.

All five:

Using vanilla = 1, strawberry = 2, chocolate = 3, the label becomes a 1 in that position:

Trivial, but it is what makes the double sum in the loss collapse — so getting the index mapping right is load-bearing. A mis-mapped class here produces a wrong loss with no visible symptom.

Only the correct class's probability survives in each term, so pick out $\hat{y}^{(i)}_{k_i}$ for each sample and take $-\log$ (natural log):

$J(\Theta) = \dfrac{1.6562 + 0.5922 + 1.1308 + 0.9909 + 0.9854}{5} = \dfrac{5.3555}{5} = \mathbf{1.0711}$

Sanity check on the magnitude: a model that guessed uniformly at random would score $-\ln(1/3) = 1.0986$. This model's loss is $1.0711$ — barely better than uniform guessing. The weights were handed to us as an arbitrary initialisation, and the number confirms they have learned essentially nothing.

(1) The probability table in Step 3. (2) The one-hot vectors in Step 4. (3) $J(\Theta) = \mathbf{1.0711}$.

Takeaways.

• Subtract the max before exponentiating. Without it you are computing $e^{42.5}$; with it, $e^0$. Shift-invariance of softmax is a provable identity, not an approximation.
• Check the sum. A softmax output summing to $0.980$ is a wrong softmax output — and that check found a real typo in the source handout.
• Compare the loss to $\ln K$. $-\ln(1/K)$ is what uniform guessing costs: $0.693$ for $K=2$, $1.0986$ for $K=3$. Any loss near that number means the model is uninformative, and knowing the landmark turns an opaque figure into a diagnosis.
• What would come next: gradient descent. The gradient of cross-entropy with respect to $\Theta$ has the famously clean form $\nabla_{\boldsymbol\theta_k} J = \frac1N\sum_i (\hat{y}^{(i)}_k - y^{(i)}_k)\mathbf{x}^{(i)}$ — predicted minus actual, times the input. Checking the argmax of each row shows this $\Theta$ predicts $(3, 2, 2, 2, 3)$ against true labels $(1, 2, 3, 3, 2)$: 1 of 5 correct, consistent with a loss at the guessing level.

Technique: softmax and cross-entropy arithmetic with numerical-stability handling. Read: Chapter 11 for softmax and cross-entropy, Chapter 9 for the gradient descent that would reduce this loss.

The two models look different: (1) has two parameter vectors, (2) has one. Showing equivalence therefore means doing two things:

1. Algebraically transform (1) into the shape of (2).
2. Identify $\boldsymbol\theta_\alpha$ in terms of $\boldsymbol\theta_1$ and $\boldsymbol\theta_2$. This is the actual content — it tells you that $K=2$ softmax has one redundant parameter vector's worth of freedom.

The single algebraic move that does it: divide numerator and denominator by the numerator. That is the whole trick, and it is worth recognising on sight because it also derives the log-odds form of logistic regression.

With $K = 2$ the softmax vector is

$\begin{bmatrix} P(Y_1 = 1 \mid \mathbf{x}^{(i)};\Theta) \\ P(Y_2 = 1\mid\mathbf{x}^{(i)};\Theta)\end{bmatrix} = \dfrac{1}{\exp\!\left(\boldsymbol\theta_1^\top\mathbf{x}^{(i)}\right) + \exp\!\left(\boldsymbol\theta_2^\top\mathbf{x}^{(i)}\right)}\begin{bmatrix} \exp\!\left(\boldsymbol\theta_1^\top\mathbf{x}^{(i)}\right) \\ \exp\!\left(\boldsymbol\theta_2^\top\mathbf{x}^{(i)}\right)\end{bmatrix}$

Both entries share the same denominator, which is why the next step works on either one.

Take the $k=1$ entry and divide top and bottom by $\exp(\boldsymbol\theta_1^\top\mathbf{x}^{(i)})$, which is strictly positive so this is always legal:

$P(Y_1 = 1\mid\mathbf{x}^{(i)};\Theta) = \dfrac{\exp\!\left(\boldsymbol\theta_1^\top\mathbf{x}^{(i)}\right)}{\exp\!\left(\boldsymbol\theta_1^\top\mathbf{x}^{(i)}\right) + \exp\!\left(\boldsymbol\theta_2^\top\mathbf{x}^{(i)}\right)}$

$= \dfrac{\exp\!\left(\boldsymbol\theta_1^\top\mathbf{x}^{(i)}\right) \big/ \exp\!\left(\boldsymbol\theta_1^\top\mathbf{x}^{(i)}\right)}{\left[\exp\!\left(\boldsymbol\theta_1^\top\mathbf{x}^{(i)}\right) + \exp\!\left(\boldsymbol\theta_2^\top\mathbf{x}^{(i)}\right)\right]\big/ \exp\!\left(\boldsymbol\theta_1^\top\mathbf{x}^{(i)}\right)}$

$= \dfrac{1}{1 + \exp\!\left(\boldsymbol\theta_2^\top\mathbf{x}^{(i)}\right)\big/\exp\!\left(\boldsymbol\theta_1^\top\mathbf{x}^{(i)}\right)}$

Now use $e^{a}/e^{b} = e^{a-b}$, and pull the $\mathbf{x}^{(i)}$ out of the difference:

$= \dfrac{1}{1 + \exp\!\left(\boldsymbol\theta_2^\top\mathbf{x}^{(i)} - \boldsymbol\theta_1^\top\mathbf{x}^{(i)}\right)} = \dfrac{1}{1 + \exp\!\left(\left(\boldsymbol\theta_2 - \boldsymbol\theta_1\right)^\top\mathbf{x}^{(i)}\right)}$

The step $\boldsymbol\theta_2^\top\mathbf{x} - \boldsymbol\theta_1^\top\mathbf{x} = (\boldsymbol\theta_2 - \boldsymbol\theta_1)^\top\mathbf{x}$ is just linearity of the dot product, but it is the step that makes the whole thing work: two parameter vectors have collapsed into one.

We have $\dfrac{1}{1 + \exp\!\left((\boldsymbol\theta_2 - \boldsymbol\theta_1)^\top\mathbf{x}^{(i)}\right)}$ and we want $\dfrac{1}{1 + \exp\!\left(-\boldsymbol\theta_\alpha^\top\mathbf{x}^{(i)}\right)}$. Matching the exponents:

$-\boldsymbol\theta_\alpha^\top\mathbf{x}^{(i)} = (\boldsymbol\theta_2 - \boldsymbol\theta_1)^\top\mathbf{x}^{(i)} \quad \text{for all } \mathbf{x}^{(i)}$

which forces

$\boxed{\boldsymbol\theta_\alpha = -(\boldsymbol\theta_2 - \boldsymbol\theta_1) = \boldsymbol\theta_1 - \boldsymbol\theta_2}$

With that definition,

$P(Y_1 = 1 \mid \mathbf{x}^{(i)};\Theta) = \dfrac{1}{1+\exp\!\left(-\boldsymbol\theta_\alpha^\top\mathbf{x}^{(i)}\right)}$

which is exactly the $k=1$ case of (2). For $k = 2$, use the fact that the two softmax outputs sum to 1:

$P(Y_2 = 1\mid\mathbf{x}^{(i)};\Theta) = 1 - \dfrac{1}{1+\exp\!\left(-\boldsymbol\theta_\alpha^\top\mathbf{x}^{(i)}\right)} = \dfrac{\left(1 + \exp(-\boldsymbol\theta_\alpha^\top\mathbf{x}^{(i)})\right) - 1}{1+\exp\!\left(-\boldsymbol\theta_\alpha^\top\mathbf{x}^{(i)}\right)}$

$= \dfrac{\exp\!\left(-\boldsymbol\theta_\alpha^\top\mathbf{x}^{(i)}\right)}{1+\exp\!\left(-\boldsymbol\theta_\alpha^\top\mathbf{x}^{(i)}\right)}$

which is exactly the $k = 2$ case of (2). Both cases match, so the models are equivalent. ■

The reduction is not a coincidence; it is a symptom of something true for every $K$.

So softmax regression has $M$ redundant degrees of freedom: the whole family $\{\boldsymbol\theta_k + \mathbf{c}\}$ represents the same model. A standard way to remove the redundancy is to fix one parameter vector at zero, say $\boldsymbol\theta_2 = \mathbf{0}$. Do that in the $K=2$ case and $\boldsymbol\theta_\alpha = \boldsymbol\theta_1 - \mathbf{0} = \boldsymbol\theta_1$ — one parameter vector, which is precisely binary logistic regression.

Numerical confirmation of the reduction itself: with the same $\boldsymbol\theta_1, \boldsymbol\theta_2$ as above, the two-class softmax probability of class 1 and the sigmoid $1/(1+e^{-\boldsymbol\theta_\alpha^\top\mathbf{x}})$ with $\boldsymbol\theta_\alpha = \boldsymbol\theta_1 - \boldsymbol\theta_2$ agree exactly — to within $10^{-12}$ — at $\mathbf{x} = (1,2,-1)$, $(1,-0.5,3)$ and $(1,0,0)$, giving $0.1679816149$, $0.1480471980$ and $0.6681877722$ respectively.

A consequence worth stating: because only the difference $\boldsymbol\theta_1 - \boldsymbol\theta_2$ affects the output, the individual values of $\boldsymbol\theta_1$ and $\boldsymbol\theta_2$ are not identifiable from data. Two training runs can land on wildly different $\Theta$ matrices and define the identical classifier. (Adding L2 regularisation breaks the tie, because among all equivalent $\Theta$ it prefers the one of smallest norm — another reason regularisation is standard practice.)

Result: $K=2$ softmax regression is binary logistic regression with

$\boldsymbol\theta_\alpha = \boldsymbol\theta_1 - \boldsymbol\theta_2.$

The derivation is one move — divide numerator and denominator by the numerator — followed by $e^a/e^b = e^{a-b}$ and the linearity of the dot product.

Takeaways.

• Softmax generalises the sigmoid, not the other way round. You can always recover the sigmoid by setting $K=2$; so anything true of softmax is true of logistic regression as a special case, which is why the lecture notes derive the softmax gradient once and reuse it.
• The divide-by-the-numerator move is the standard way to turn a ratio of exponentials into a sigmoid, and it appears again when you derive the log-odds form.
• Only differences of parameter vectors matter. That is what makes the reduction possible and it is also why softmax parameters are not individually interpretable.

Technique: deriving a model reduction, and recognising over-parameterisation. Read: Chapter 11 — the same exercise appears there, and Chapter 12 explains why regularisation resolves the non-identifiability.

Three things, and the comparison is what earns the marks: the definitions are one line each, but "which one would you use and why" is the question that follows on an exam.

Frame: regularization adds a penalty on the size of $\boldsymbol\theta$ to the objective, so that minimising it trades fit against simplicity. The norm you pick decides what "simple" means.

A flexible model can fit the training set too closely — memorising it rather than learning the pattern — and then generalises badly. Regularization attacks that directly by penalising complexity, pushing the optimiser towards simpler parameter vectors that do better on unseen data.

The objective becomes

$J_{\text{reg}}(\boldsymbol\theta) = \underbrace{J(\boldsymbol\theta)}_{\text{fit the data}} + \lambda \underbrace{R(\boldsymbol\theta)}_{\text{stay simple}}$

where $\lambda \ge 0$ sets the exchange rate. $\lambda = 0$ recovers the unregularized model; $\lambda \to \infty$ drives $\boldsymbol\theta \to \mathbf{0}$ and the model predicts a constant. $\lambda$ is a hyperparameter, so it is chosen on a validation set, never on the training set — training error is monotonically increasing in $\lambda$, so training error can only ever tell you to pick $\lambda = 0$.

Quick worked comparison on $\mathbf{x} = (3, 0, -4)$:   $\lVert\mathbf{x}\rVert_2 = \sqrt{9 + 0 + 16} = 5$;   $\lVert\mathbf{x}\rVert_1 = 3 + 0 + 4 = 7$;   $\lVert\mathbf{x}\rVert_0 = 2$. Note L0 does not change if you scale $\mathbf{x}$ by 100, while the other two scale by 100.

Sparsity. L0 and L1 encourage sparsity — many parameters driven exactly to zero. L2 prefers parameters that are all small but generally none exactly zero.

Why: L2's gradient with respect to $\theta_i$ is $2\theta_i$, which vanishes as $\theta_i \to 0$, so the pressure to shrink disappears just as the parameter approaches zero — it is shrunk but never pinned. L1's gradient is $\mathrm{sign}(\theta_i)$, constant magnitude 1 all the way in, so a parameter whose contribution to the fit is worth less than $\lambda$ is pushed exactly to zero and stays there.

Optimisation. L1 and L2 are tractable to optimise; L0 is not.

• L2 is differentiable everywhere and convex — the easiest case. With squared error it even keeps a closed-form solution (Problem 5.6).
• L1 is convex but not differentiable at 0, so it needs subgradients or proximal methods. Still efficiently solvable.
• L0 is neither convex nor differentiable — it is piecewise constant, so its gradient is zero almost everywhere and carries no information. Minimising it exactly requires combinatorial search over which subset of parameters is non-zero, which is intractable for realistic $M$. This is why L1 is used as a proxy for L0: it is the tightest convex relaxation that still induces sparsity.

The handout's own summary of this, restated: L0 and L1 give sparsity while L2 gives small-but-nonzero; L1 and L2 are optimisable while L0 is not. L1 is the only one in both good columns, which is exactly why it is the standard choice when you want feature selection, and L2 the standard choice when you simply want stability.

Technique: regularization as explicit complexity control, and the sparsity/tractability trade-off between norms. Read: Chapter 12 — Regularization & cross-validation.

Problem 4.4 again, with one extra term. So: expand, differentiate with the same two identities, set to zero, solve. The only new work is $\partial(\lambda\boldsymbol\theta^\top\boldsymbol\theta)/\partial\boldsymbol\theta$, and one subtle step at the very end where a scalar has to become a matrix.

Note this objective has no $1/N$ factor, unlike Problem 4.4's. That changes nothing structurally — it only rescales what a given $\lambda$ means, which is worth being aware of when comparing $\lambda$ values across formulations.

Use $\lVert\mathbf{a}\rVert_2^2 = \mathbf{a}^\top\mathbf{a}$ on both terms:

$J(\boldsymbol\theta) = (\mathbf{y} - X\boldsymbol\theta)^\top(\mathbf{y}-X\boldsymbol\theta) + \lambda\boldsymbol\theta^\top\boldsymbol\theta$

Expand the first product, remembering $(X\boldsymbol\theta)^\top = \boldsymbol\theta^\top X^\top$:

$= \mathbf{y}^\top\mathbf{y} - \mathbf{y}^\top X\boldsymbol\theta - \boldsymbol\theta^\top X^\top\mathbf{y} + \boldsymbol\theta^\top X^\top X \boldsymbol\theta + \lambda\boldsymbol\theta^\top\boldsymbol\theta$

The two middle terms are equal: each is a $1\times1$ scalar, and one is the transpose of the other, and a scalar equals its own transpose. So they combine:

$J(\boldsymbol\theta) = \mathbf{y}^\top\mathbf{y} - 2\boldsymbol\theta^\top X^\top\mathbf{y} + \boldsymbol\theta^\top X^\top X\boldsymbol\theta + \lambda\boldsymbol\theta^\top\boldsymbol\theta$

which is Problem 4.4's expansion plus $\lambda\boldsymbol\theta^\top\boldsymbol\theta$. That "a scalar equals its transpose" step is small and is where marks get lost if it is skipped silently.

Term by term, as in 4.4, and for the new term note $\boldsymbol\theta^\top\boldsymbol\theta = \boldsymbol\theta^\top I \boldsymbol\theta$ is a quadratic form with $A = I$, so $(A^\top + A)\boldsymbol\theta = 2I\boldsymbol\theta = 2\boldsymbol\theta$:

$\nabla J(\boldsymbol\theta) = -2X^\top\mathbf{y} + 2X^\top X\boldsymbol\theta + 2\lambda\boldsymbol\theta = -2X^\top(\mathbf{y} - X\boldsymbol\theta) + 2\lambda\boldsymbol\theta$

Shape check: every term is $M \times 1$. ✓

$-2X^\top(\mathbf{y} - X\boldsymbol\theta) + 2\lambda\boldsymbol\theta = \mathbf{0}$

Divide by 2 and expand:

$-X^\top\mathbf{y} + X^\top X \boldsymbol\theta + \lambda\boldsymbol\theta = \mathbf{0} \qquad \Longrightarrow \qquad X^\top X \boldsymbol\theta + \lambda\boldsymbol\theta = X^\top\mathbf{y}$

Now factor out $\boldsymbol\theta$. Here is the step that needs care:

$\left(X^\top X + \lambda I\right)\boldsymbol\theta = X^\top \mathbf{y}$

$\boxed{\boldsymbol\theta = \left(X^\top X + \lambda I\right)^{-1}X^\top\mathbf{y}}$

Numerical verification. On the same 4-point dataset as Problem 4.4 with $\lambda = 0.5$, this formula gives $\boldsymbol\theta = (0.7248,\ 1.0738)$, and the numerical gradient of the regularized objective at that point is zero to 9 decimal places. Compare the unregularized solution, $(1.0,\ 1.0)$: the regularized one has smaller total norm, and the intercept has been pulled hardest toward 0, which is the expected behaviour.

$\boldsymbol\theta = \left(X^\top X + \lambda I\right)^{-1}X^\top\mathbf{y}$

Compare with the unregularized $\boldsymbol\theta = (X^\top X)^{-1}X^\top\mathbf{y}$: regularization adds $\lambda I$ to the matrix being inverted, and nothing else changes. This is why the method is called ridge regression — it adds a ridge along the diagonal.

Takeaways.

• It fixes invertibility. Problem 4.4's caveat was that $X^\top X$ can be singular — duplicated features, or $M > N$. Adding $\lambda I$ with $\lambda > 0$ makes the matrix strictly positive definite and therefore always invertible. So ridge regression has a unique closed-form solution even when ordinary least squares has none. That is a practical reason to regularize that has nothing to do with overfitting.
• $\lambda$ interpolates. $\lambda = 0$ recovers OLS; $\lambda \to \infty$ drives $\boldsymbol\theta \to \mathbf{0}$. Choose it on a validation set.
• Why L2 and not L1 here. $\lVert\boldsymbol\theta\rVert_2^2$ is differentiable, so the gradient is linear in $\boldsymbol\theta$ and the stationarity condition is a linear system with a closed-form answer. L1 is not differentiable at 0, so lasso has no closed form and needs an iterative solver — the exact trade-off Problem 5.5 describes, now visible in the algebra.
• In practice, do not penalise the bias. The intercept should be free to match the mean of $\mathbf{y}$; standard implementations use $\lambda I$ with a zero in the bias position. The exam version usually ignores this, but it is worth a sentence if you have room.

Technique: deriving a regularized closed-form estimator, with correct scalar-to-matrix promotion. Read: Chapter 12 for ridge and the choice of $\lambda$, and Chapter 8 for the unregularized baseline.