Practice Questions with Worked Solutions

A human judge holds a text conversation with a human and a machine. If the judge cannot reliably tell which is which, the machine passes. It tests indistinguishable behaviour, not thought.

Weak (narrow) AI performs one task without understanding — every system in use today. Strong (general) AI would possess general understanding across domains; none exists.

One that, for each percept sequence, selects the action expected to maximise its performance measure, given its built-in knowledge. Rationality is not omniscience — a rational agent can still lose.

Performance measure, Environment, Actuators, Sensors.

Chess is deterministic; taxi driving is stochastic.

Initial state, actions (successor function), goal test, path cost.

Only when every step costs the same. It minimises the number of edges, and edges equal cost only under uniform step costs.

BFS O(b^d); DFS O(bm). That difference — exponential against linear — is DFS's only real advantage.

Dijkstra's algorithm. Same procedure, reached from the AI side.

h(n) never overestimates the true remaining cost h*(n): h(n) ≤ h*(n) for every n.

h(n) ≤ c(n, n′) + h(n′) for every edge. Consistency implies admissibility; the reverse does not hold.

f(n) = g(n) + h(n) — cost paid plus cost estimated.

Uniform cost search — verified identical: 13 expansions, cost 418 on Romania.

It ignores g(n). At Sibiu it prefers Fagaras (h = 176) over Rimnicu Vilcea (h = 193) and ends 32 km worse — 450 against 418.

Local maxima. Measured here: 10 of 21 starting points (48%) get stuck.

Random restarts. Expected restarts = 1/p, about 1.9 on this landscape.

e^(−ΔE/T). For ΔE = 1: 0.990050 at T = 100 and 0.000045 at T = 0.1.

Selection, crossover, mutation.

A set of variables, each with a domain, and a set of constraints on subsets of them. A solution assigns every variable a value violating no constraint.

Minimum Remaining Values. It chooses the next variable — the one with fewest legal values left.

Least Constraining Value. It orders the values of the chosen variable.

Variables: fail fast. Values: fail late. You want to discover a dead end early, but once committed to a value you want it to survive.

WA, NT and SA are mutually adjacent — a triangle. Two colours give no solution, discovered after 4 backtracks.

92, found after 2,056 placements.

Yes — vacuously. P ⇒ Q ≡ ¬P ∨ Q.

Valid = true in every model (P ∨ ¬P, 8/8). Satisfiable = true in at least one (P ∧ Q, 2/8). Unsatisfiable = true in none (P ∧ ¬P, 0/8).

P ⇒ Q, P ⊢ Q. P ⇒ Q, ¬Q ⊢ ¬P.

Row (F, T) of the truth table: P false, Q true, P ⇒ Q true. So Q does not force P.

KB ⊨ α when α is true in every model of KB. Equivalently KB ∧ ¬α is unsatisfiable — the form resolution mechanises.

Finding a substitution making two expressions identical: Knows(John, x) and Knows(y, Mary) unify with {x/Mary, y/John}.

∀ pairs with ⇒, ∃ pairs with ∧. ∀x Student(x) ∧ Smart(x) claims everything is a smart student.

Backward — many facts, one question.

\+ G succeeds if G cannot be proved. It assumes a closed world and is not logical negation: \+ bird(kiwi) succeeds only because no one said so.

A cut whose removal changes the answers, not just the speed.

Knowledge base, inference engine, working memory, explanation facility (plus a knowledge-acquisition interface).

P(H|E) = P(E|H) · P(H) / P(E).

Conditional independence of the features given the class.

An unseen feature–class pair gives likelihood 0, which vetoes the class because the likelihood is a product. Fix: Laplace smoothing — 0.0 becomes 0.044643 here.

Probability measures uncertainty about a crisp fact; fuzzy membership measures degree of truth of a vague predicate. A 0.7 chance of rain is not 0.7 rain.

Search is given a description of the problem and explores it; learning is given examples and fits a function. Nothing in this course is trained.

PEAS specifies an agent before you design it.

For an automated taxi:

Environment classification:

Measured on the Romania map, Arad → Bucharest:

Read it as a trade: DFS did the least work and found the worst path; UCS did the most work and found the best. BFS minimised edges, which is not the same as cost — the guarantee it offers does not apply here.

The counterexample to "BFS is optimal": on a six-node graph with unit costs, BFS and UCS both return cost 2. Raise one edge to 50 and BFS returns 51 where UCS returns 4.

IDS runs depth-limited DFS with limit 0, 1, 2, … until the goal is found. It has DFS's memory and BFS's guarantee.

The obvious objection is that it regenerates the upper levels every time. With b = 10, d = 5:

11.1% more nodes, 2,000× less memory. The repetition is cheap because the bottom level holds most of the nodes — regenerating everything above it costs almost nothing. IDS is the uninformed search of choice when depth is unknown.

h is admissible if h(n) ≤ h*(n) everywhere. A* then never expands a node whose f exceeds the optimal cost, so it cannot return a worse goal.

Measured on Romania:

The inadmissible heuristic was faster and wrong. Overestimating makes a node on the optimal path look worse than an alternative, so A* commits to a goal before the better route is explored.

Verification, not assertion: checked at all 20 cities, straight-line violated admissibility 0 times, h(Bucharest) = 0, and the tightest margin h*(n) − h(n) was 1 km. The ×2 heuristic violates at 18 of 20.

The general argument: a straight line can never be longer than a road. Admissible by construction, not by luck.

h1 = misplaced tiles. h2 = sum of Manhattan distances.

Both are admissible because both solve a relaxed problem — h1 lets a tile teleport, h2 lets it move to any adjacent square, ignoring the blank. A relaxed-problem solution can never cost more than the real one.

h2 ≥ h1 everywhere, so h2 dominates h1, and A with h2 expands no more nodes than A with h1. Dominance is a stronger and more precise claim than "it was faster on my example" — and it explains why you would derive heuristics by relaxing constraints.

Forward (data-driven): apply every rule whose premises hold, add the conclusions, repeat. From {a, b} and 3 rules it derived ['c', 'd', 'e'] — everything derivable, wanted or not.

Backward (goal-driven): to prove e, prove its premises; recurse. Proving e needed d, which needed c, which needed a and b — and nothing outside that chain.

Prolog is backward chaining with depth-first search. That single sentence explains why clause order matters and why a left-recursive rule never terminates.

Formulation:

Modelling the blank rather than the tiles cuts the branching factor from about 20 to under 4. This is the modelling decision the question is really testing.

State space size: 9! = 362,880 arrangements, of which only half are reachable from any given state — parity is invariant under a blank move, so 181,440 configurations are unsolvable from a given start. Never claim 9! without that.

Heuristics — h1 misplaced tiles, h2 Manhattan distance, both admissible by relaxation, h2 dominant (6 against 14 on a scrambled board).

A* on the Romania map — the same algorithm, verified: 6 expansions, cost 418, against UCS's 13 expansions, cost 418. Same optimal answer, less than half the work.

The failure mode: double h2 and A expands 4 nodes and returns 450 instead of 418. Speed bought by breaking admissibility is not speed, it is a different algorithm.*

Measured, honestly:

The heuristics saved nothing on this problem, and saying so is worth marks. The reason: SA borders every mainland region, so once SA is assigned every neighbour has only two values — and the plain ordering happens to reach SA early too. On a larger map the orderings diverge.

What the heuristics do:

After WA = red, values remaining:

• MRV picks NT — fewest values, most likely to fail, so fail fast.
• Degree breaks the NT/SA tie by constraint count — SA has 5 neighbours.
• LCV then orders NT's values ['green', 'blue'], least constraining first — fail late, because you want the committed value to survive.

With two colours: no solution, after 4 backtracks. WA, NT, SA form a mutually adjacent triangle. The search proves insolubility by exhausting the space, which is what "no solution" means for a CSP — it is not a timeout.

Syntax: atomic propositions, and the connectives ¬, ∧, ∨, ⇒, ⇔ with precedence in that order.

Semantics: a model assigns true/false to every proposition. A sentence is true or false in a model; n propositions give 2^n models.

The truth table:

The two rows people get wrong are the first two. P ⇒ Q is true whenever P is false, because it claims only there is no case where P holds and Q fails. That is exactly ¬P ∨ Q, verified over all 4 models — and it is step 2 of the CNF conversion, so resolution depends on it.

Three status classes, over the 8 models of P, Q, R:

Entailment: KB ⊨ α when α holds in every model of KB. Measured: {P, P⇒Q} has 2 models and Q holds in both, so {P, P⇒Q} ⊨ Q.

The refutation form: KB ⊨ α iff KB ∧ ¬α is unsatisfiable — zero models. This is what resolution mechanises, because searching for one contradiction is cheaper than checking all models.

Inference rules: modus ponens (P⇒Q, P ⊢ Q) and modus tollens (P⇒Q, ¬Q ⊢ ¬P), both verified over all 4 models. Affirming the consequent (P⇒Q, Q ⊢ P) is invalid, and the table names the counterexample: row (F, T).

Soundness and completeness: an inference procedure is sound if it derives only entailed sentences and complete if it derives every entailed sentence. Resolution is both, for propositional logic.

The limitation that forces FOL: propositional logic has no objects and no quantifiers, so "every student who studies passes" needs one sentence per student. A world of n objects and k properties needs n·k propositions.

Architecture:

The separation of knowledge from inference is the architectural point — a domain expert edits rules without touching code, which is why expert systems were commercially viable when general AI was not.

The system, implemented and run:

viral(X)        :- fever(X), cough(X).
flu(X)          :- viral(X), fatigue(X).
bacterial(X)    :- fever(X), rash(X).
rest_advised(X) :- flu(X).

Working memory: fever, cough, fatigue. Results, through real SLD resolution:

?- viral(patient)         -> Yes
?- flu(patient)           -> Yes
?- rest_advised(patient)  -> Yes
?- bacterial(patient)     -> not derivable (no rash recorded)

The explanation:

HOW did you conclude rest_advised(patient)?
  by rule  rest_advised(X) :- flu(X)
  flu(patient)     by  flu(X) :- viral(X), fatigue(X)
    viral(patient) by  viral(X) :- fever(X), cough(X)
      fever(patient)   -- a fact in working memory
      cough(patient)   -- a fact in working memory
    fatigue(patient)   -- a fact in working memory

The chain is the explanation, and it falls out of the proof for free. A neural network can output "flu, 0.94" and nothing more. Add rash and bacterial(patient) becomes derivable — the conclusion changes and the system can name the fact that changed it.

WHY questions are the other direction: when the system asks for a symptom, "why do you need this?" is answered by the rule currently being proved.

Limitations, which the question expects:

• The knowledge acquisition bottleneck — the expert's time is the cost, and it does not scale.

• Brittleness — no graceful degradation at the edge of the rule set. It does not know what it does not know.

• No learning — it never improves from cases it has seen.

• Rule interaction — beyond a few hundred rules, conflicts become unmanageable, which is what ended the 1980s expert-system boom.

Bayes' theorem: P(H|E) = P(E|H)·P(H) / P(E) — posterior = likelihood × prior / evidence.

Naive Bayes classifies by argmax over classes of P(c) · ∏ P(feature_i | c), assuming the features are conditionally independent given the class. That assumption is nearly always false, and it works anyway because classification needs only the correct class to rank first, not the probabilities to be right.

Worked, on the 14-day play-tennis data — 9 play, 5 do not. Query: outlook = sunny, temperature = cool, humidity = high, wind = strong.

Normalised: no = 79.54%, yes = 20.46%. Predict NO.

The zero-frequency problem: overcast never appears with play = no, so P(overcast | no) = 0 and

P(no | overcast, ...) without smoothing = 0.0
with Laplace (+1, 3 outlook values)     = 0.044643

One zero vetoes the class whatever the other three features say, because the likelihood is a product. Laplace smoothing adds 1 to each count and k (the number of values the feature takes — here 3) to each denominator.

Cross-course verification: these are Data Mining's numbers and Machine Learning's numbers. Three courses, three independent implementations, the same 0.005291 and 0.020571 — and tools/data-science/verify_all.sh fails if they ever drift.

Bayesian belief networks generalise this: a directed acyclic graph where each node carries P(node | parents), and the joint distribution factorises as the product of those tables. Naive Bayes is the special case in which every feature has the class as its single parent — which is exactly what conditional independence means, drawn.

Where classical AI is still the right answer:

• The rules are known and stated — tax law, drug interaction checking, scheduling. Learning them from examples would be perverse.

• The decision must be justified. A triage system that cannot explain itself is not deployable, whatever its accuracy.

• There are no examples to learn from — a chess position never seen, a timetable never built.

Where it fails: perception. No one writes rules that recognise a cat, and the attempt is what caused the second AI winter.

The honest modern position: the two are combined. A chess engine searches with a learned evaluation function; a self-driving car uses learned perception and a planned route. Search supplies the guarantee, learning supplies the model — and each covers what the other cannot.