5 · MCQ concepts: Poole–Mackworth ch 3–5 + data structures

15 MCQs at 0.5 points each. On Exam 1, about half were Poole–Mackworth (PM) one-line definitions and half were quick DPV facts. This page is the definitions and the "exam phrasing → answer" rules. Drill them on the MCQ drill bank.

How to answer a definition MCQ in 30 seconds.

Find the one keyword in the stem ("arc costs", "heuristic", "fewest arcs", "linear space", "every model", "can't be proved").
Map it with the tables below.
Be suspicious of "All of the above" when one option describes a different property (Exam 1 Q9: deterministic ≠ fully observable).
If two options are both true but one is tight, pick the tight one (Exam 1 Q17: \(O(n)\) over \(O(2^n)\)).

Classic traps (read these twice)

Trap statement	Truth
"F → T is false."	Wrong. \(p \to q\) is false only when p is T and q is F. F → T and F → F are both T.
"A definite-clause query answered no means the atom is false."	Wrong. "No" means not entailed: the atom is false in the minimal model but true in other models.
"GAC left every domain non-empty, so a solution exists."	Wrong. Non-empty but not all singletons means "don't know yet". Example: X, Y, Z ∈ {red, green}, all pairs ≠: GAC deletes nothing, no solution.
"Local search ran an hour without success, so there is no solution."	Wrong. Local search is incomplete: it can never prove unsatisfiability.
"BFS needs memory linear in solution depth."	Wrong. BFS memory is exponential, \(O(b^d)\). DFS (and iterative deepening, DF branch and bound) is linear, \(O(bd)\).
"A* always returns an optimal path."	Only if h is admissible (never overestimates), the branching factor is finite and arc costs are bounded above zero.
"Iterative deepening wastes most of its time redoing shallow levels."	Wrong. Overhead is a constant factor, about \(b/(b-1)\): the last level dominates.
"Dijkstra works with negative edges if there are no negative cycles."	Wrong. One negative edge can improve an already-finalized vertex. Use Bellman–Ford (or the DAG pass if acyclic).
"Add a constant to every edge to remove negative lengths, then run Dijkstra."	Wrong (DPV 4.8). Adding c adds \(c \cdot (\#\text{edges})\), so paths with more edges are penalized and shortest paths change. Multiplying every length by a positive constant does not change them.
"DFS from s finds distances."	Wrong. BFS does (unit lengths). DFS depth is not distance.
"O(nW) knapsack is polynomial."	Pseudo-polynomial: W takes only \(\log W\) bits to write.
"Greedy by value/weight is optimal for 0/1 knapsack."	Only for fractional knapsack.
"A contradictory KB entails nothing."	It entails everything (no models, so g is true in all of them vacuously).
"Adding facts can only add conclusions."	False with negation as failure: it is nonmonotonic.
"Every valid proposition is satisfiable" / "every satisfiable one is valid."	First is true; second is false (p → q is satisfiable, not valid).
"Hash table search is O(1)."	Expected \(O(1)\) under assumptions (simple uniform / universal hashing). Worst case \(\Theta(n)\).

Exam 1 PM recap (ch 1–2, lower priority now)

Phrase	Answer
Inputs to an agent	Abilities, goals/preferences, prior knowledge, past experiences, observations ("All of the above")
Deterministic	Next state is predictable from current state + action (not "knows its state": that is full observability)
Memory of the past used for current and future actions	Belief state
Search that uses arc costs	Lowest-cost-first (also A*, which adds a heuristic)
Search that uses a heuristic function	A* (also greedy best-first)

PM ch 3: searching for solutions

Vocabulary

Term	Meaning
Frontier	The set of paths generated but not yet expanded. The strategy = how you pick from it.
Branching factor b	Number of neighbours (forward branching factor) of a node.
Heuristic h(n)	Estimate of the cost of the cheapest path from n to a goal. Non-negative, cheap to compute.
Admissible h	Never overestimates: \(h(n) \le\) actual cost of the cheapest path from n to a goal. \(h \equiv 0\) is admissible (and useless).
Consistent (monotone) h	\(h(n) \le \text{cost}(n, n') + h(n')\). Consistent implies admissible (with h(goal) = 0). Needed so multiple-path pruning keeps A* optimal.
Cycle pruning	Discard a path whose last node already appears earlier on that same path. Cheap.
Multiple-path pruning	Keep an explored set (closed list); discard a path to a node already reached. Can cost exponential memory, like BFS.
Iterative deepening	Depth-bounded DFS with bound 1, 2, 3, …. Linear space and finds fewest-arc paths; overhead factor about \(b/(b-1)\).
Depth-first branch and bound	DFS that keeps the best solution cost so far as a bound; prunes a path p when \(\text{cost}(p) + h(p) \ge\) bound (h admissible). Linear space; finds a least-cost path given an initial bound above the optimum.
Greedy best-first	Pick the path whose end has smallest h(p), ignoring cost so far. Not guaranteed to find a path or the best one.

Strategy summary (PM Figure 3.18)

Strategy	Selects from frontier	Path found (guaranteed)	Space
Breadth-first	first added (FIFO queue)	fewest arcs	\(O(b^d)\) exponential
Depth-first	last added (LIFO stack)	none (can follow an infinite path)	\(O(bd)\) linear
Iterative deepening	n/a	fewest arcs	\(O(bd)\)
Greedy best-first	min h(p)	none	\(O(b^d)\)
Lowest-cost-first	min cost(p) (priority queue)	least cost	\(O(b^d)\)
A*	min cost(p) + h(p)	least cost (h admissible)	\(O(b^d)\)
DF branch and bound	n/a	least cost	\(O(bd)\)

"Path found" assumes finite branching factor and arc costs bounded above zero.

Exam phrasing → answer

"uses a FIFO queue" / "fewest arcs" / "shallowest goal" → BFS.
"uses a stack" / "linear memory" / "may not halt on infinite graphs" / "good when all solutions are at the same depth (CSPs)" → DFS.
"linear memory and fewest arcs" → iterative deepening.
"considers arc costs", no heuristic → lowest-cost-first (= Dijkstra on an implicit graph).
"cost so far + estimate to goal" → A*. With \(h \equiv 0\), A* = lowest-cost-first.
"estimate only" → greedy best-first.
"never overestimates" → admissible. "satisfies a triangle inequality on arcs" → consistent.
"prune when the bound is reached, linear space, optimal" → DF branch and bound.

PM ch 4: reasoning with constraints

Term	Meaning
Possible world	A total assignment: a value for every variable. Count = product of domain sizes (\(d^n\) if all equal).
Constraint	Scope (set of variables) + relation. Intensional (formula, A < B) or extensional (table of allowed tuples).
Unary / binary / k-ary	Scope of size 1 / 2 / k. B ≠ 3 unary; A = D binary; X + Y = Z ternary; alldifferent(9 cells) 9-ary.
Model (solution)	A possible world satisfying every constraint.
Generate-and-test	Check every total assignment. Correct, exponential.
Backtracking	DFS over partial assignments; check a constraint as soon as its whole scope is assigned; prune on failure.
Forward checking	After assigning, delete now-impossible values from unassigned neighbours; back up if one becomes empty.
Most constrained variable (MRV)	Pick the variable with the fewest remaining values ("fail first"). Ties: most constraining variable (most constraints with unassigned variables).
Least constraining value	Try first the value ruling out the fewest neighbour values ("succeed first").
Arc <X, c> consistent	Every value of X has a support: values of c's other variables satisfying c.
GAC	To-do list of arcs; prune unsupported values; when dom(X) shrinks, re-add <Z, c'> for every other constraint c' on X and other variable Z in c'. Final domains don't depend on arc order. Binary: \(O(cd^3)\).
Domain splitting	Split a domain into cases, rerun GAC on each. With GAC, complete.
Variable elimination	Join all constraints on X, project X out. Cost = largest relation built; depends on elimination order (treewidth).
Local search	Start from a total assignment; move to neighbours to reduce h = number of violated constraints. Scales; incomplete.
Local minimum / plateau	All neighbours worse / all neighbours equal.
Random restart / random walk	Big jump (new random assignment) / small random move with probability p.
Tabu list	Don't undo any of the last t changes; avoids cycling on plateaus.
Simulated annealing	Accept a worse move by Δ with probability \(e^{-\Delta/T}\); lower T over time. High T ≈ random walk, low T ≈ greedy.
Beam / stochastic beam / GA	Keep k best / keep k chosen at random weighted by quality / crossover + mutation of parents.
Runtime distribution	Fraction of runs solved within k steps. Restarts every k steps with success q: fail r times in a row with probability \((1-q)^r\).
Soft constraint / branch and bound	Cost function on scope; minimize total. Prune partial assignment whose lower bound ≥ best found.

GAC: three outcomes

When GAC stops	Conclusion
Some domain empty	No solution.
Every domain a singleton	That assignment is the unique solution.
Some domain has ≥ 2 values	Unknown: 0, 1 or many solutions. Split and recurse.

Quick GAC on \(A < B\), both {1,2,3,4}: A loses 4, B loses 1. On \(A \le B - 2\): A = {1, 2}, B = {3, 4}.

PM ch 5: propositions and inference

Term	Meaning
Interpretation	Assigns T/F to every atom. n atoms → \(2^n\) interpretations.
Model of KB	Interpretation making every proposition in KB true.
Valid / satisfiable / unsatisfiable	True in all / some / no interpretations. p ∨ ¬p / p → q / p ∧ ¬p.
KB ⊨ g (entails)	g true in every model of KB. Semantic. Equivalent: KB ∪ {¬g} unsatisfiable.
KB ⊢ g (derives)	A proof procedure derives g. Syntactic.
Sound	KB ⊢ g ⇒ KB ⊨ g (derives only consequences).
Complete	KB ⊨ g ⇒ KB ⊢ g (derives all consequences).
Clause / DPLL	Disjunction of literals. DPLL = backtracking + unit propagation (+ pure symbols). Unit propagation is arc consistency for clauses.
Definite clause	h ← a1 ∧ … ∧ am, exactly one atom in the head. m = 0: a fact. Cannot say anything is false; always has a minimal model.
Bottom-up (forward chaining)	Fire clauses whose bodies are derived until fixpoint. Result = minimal model. Sound and complete for atoms; linear time. Derives everything.
Top-down (SLD resolution)	Start with yes ← query; replace a selected atom by a clause body; success at "yes ←". Only touches relevant clauses; depth-first can loop (a ← b, b ← a).
Askable atom	The user is asked about it only when a proof needs it.
Integrity constraint	false ← a1 ∧ … ∧ ak. Definite clauses + integrity constraints = Horn clauses. A Horn KB can be inconsistent.
Assumable / conflict	Atom assumed true unless contradicted / set of assumables that with KB implies false. Minimal if no proper subset is a conflict.
Consistency-based diagnosis	Minimal hitting set of the minimal conflicts.
Complete knowledge assumption	The clauses for a are the only ways a can be true: Clark's completion a ↔ b1 ∨ … ∨ bn. Atom with no clauses is false.
Negation as failure ~a	Succeeds when a cannot be proved. Nonmonotonic.
Abduction	Explanation of g: set H of assumables with KB ∪ H ⊨ g and KB ∪ H consistent. Effects → possible causes.
Causal vs evidential	Causal: effect ← cause (lit_l1 ← live_w1 ∧ ok_l1). Evidential: cause ← effect (fire ← smoke).
Knowledge-level debugging	Incorrect answer: find a clause with true body and false head. Missing answer: a true atom with no clause whose body is all true. Uses only the intended interpretation.

Exam phrasing → answer

"true in every model of KB" → logical consequence / entailment.
"never derives something that doesn't follow" → sound; "derives everything that follows" → complete.
"one big KB, one query" → top-down; "derive all consequences once" → bottom-up.
"missing fact taken as false" (flight database) → complete knowledge assumption / negation as failure.
"adding a fact removed a conclusion" → nonmonotonic.
"which set of broken parts explains the observations" → minimal diagnosis = minimal hitting set of conflicts.
"wet grass, so maybe it rained" → abduction (not deduction).
Entailment quick checks: {p→q, p} ⊨ q (modus ponens) yes; {p→q, ¬q} ⊨ ¬p (modus tollens) yes; {p→q, q} ⊨ p no; {p ∨ q, ¬p} ⊨ q yes; {p, ¬p} ⊨ anything yes.

DPV and data structures: one-line facts

DFS (ch 3)

Adjacency lists: DFS/BFS \(O(V+E)\). Adjacency matrix: \(O(V^2)\). Edge test: matrix O(1), lists O(deg u).
Undirected DFS: only tree and back edges. Outer-loop calls to explore = number of connected components.
Directed edge (u, v): tree/forward/cross have post(u) > post(v); only back edges have post(u) < post(v). Cross edges point to an already-finished vertex.
Intervals [pre, post] are nested (ancestor) or disjoint, never partially overlapping.
Cycle ⇔ back edge. DAG: decreasing post = topological order; highest post = a source, lowest post = a sink.
Every DAG has a source and a sink. Meta-graph of SCCs is a DAG. A DAG with V vertices has V SCCs.
SCC algorithm: DFS on \(G^R\), then explore G in decreasing post (of \(G^R\)) order. Highest post in G lies in a source SCC of G. \(O(V+E)\).

Shortest paths (ch 4)

Algorithm	Lengths	Time
BFS (FIFO queue)	unit	\(O(V+E)\)
Dijkstra, binary heap	≥ 0	\(O((V+E)\log V)\)
Dijkstra, unsorted array	≥ 0	\(O(V^2)\), better for dense graphs
Dijkstra, Fibonacci heap	≥ 0	\(O(V\log V + E)\)
Bellman–Ford	any, detects negative cycles	\(O(VE)\)
DAG: linearize + one pass	any (acyclic)	\(O(V+E)\); longest path by negating or max

Dijkstra = BFS with the queue replaced by a priority queue. Calls: V deletemin, V insert, up to E decreasekey. Prim has the same running time.
Subpaths of shortest paths are shortest paths.
Bellman–Ford: a V-th round that still changes something ⇒ a negative cycle reachable from s. Can stop early if a round changes nothing.
Arbitrage: \(\ell = -\log r\), look for a negative cycle.
Scaling all lengths by \(c > 0\): shortest paths unchanged. Adding c: they can change.

Heaps / priority queues

Operation (binary min-heap, n keys)	Time
find-min (root)	O(1)
insert, deletemin, decreasekey	O(log n): bubble up/sift down along height \(\lfloor\log_2 n\rfloor\)
build heap from n keys	Θ(n)
heap sort	O(n log n)

Array layout (1-indexed): children of i at 2i and 2i + 1, parent at \(\lfloor i/2 \rfloor\). d-ary heap: deletemin \(O(d\log n/\log d)\), insert/decreasekey \(O(\log n/\log d)\).

Hash tables

Dictionary ADT: search, insert, delete. Expected O(1), worst Θ(n). Table size proportional to keys stored, not universe.
Direct-address table: slot k for key k; O(1) everything, wastes memory when universe ≫ keys.
Chaining: collisions in a linked list. Load factor α = n/m (average chain length). Insert O(1).
Division \(h(k) = k \bmod m\): fast; avoid \(m = 2^p\) (uses only low bits); choose a prime not near a power of 2.
Multiplication \(h(k) = \lfloor m(kA \bmod 1)\rfloor\), \(0 < A < 1\): not sensitive to m, slower. Easy when \(m = 2^p\).
Universal family: for \(k \ne l\), at most \(|\mathcal H|/m\) functions collide them (collision probability ≤ 1/m). Defeats adversarial keys. Chaining + universal ⇒ expected O(1) search.
Open addressing: keys stored in the table; probe sequence. Linear \((h'(k)+i) \bmod m\) → primary clustering. Quadratic \((h'(k)+c_1 i + c_2 i^2) \bmod m\) → secondary clustering. Double hashing \((h_1(k) + i\,h_2(k)) \bmod m\), \(h_2(k)\) relatively prime to m.

Union-find (DPV §5.1.4)

makeset, find, union. Union by rank: attach the lower-rank root under the higher; rank = height; a rank-k root has ≥ \(2^k\) nodes, so height ≤ log n and find is O(log n).
Path compression: amortized \(O(\log^* n)\) per operation.
Kruskal: sort edges O(m log m) = O(m log n), 2m finds, exactly n − 1 successful unions.

ADTs (week 6, Morin)

ADT	Operations / policy
Queue (FIFO)	add-last + remove-first. BFS.
Stack (LIFO)	push = add-last, pop = remove-last. DFS.
Priority queue	remove by priority. Heap. Dijkstra, Prim, Huffman.
Deque	add-first, remove-first, add-last, remove-last.
List	size, get(i), set(i,y), add(i,x), remove(i). add-first = add(0,x); remove-last = remove(size()−1).
USet	size, add, remove, find; unique, unordered. Dictionary/map = USet of (key, value) pairs.
SSet	Total order; find(x) = successor search: smallest y ≥ x, or null.

Array-based: O(1) get/set. Pointer-based: faster insert/delete.

Greedy (ch 5)

Needs greedy-choice property + optimal substructure. Prove by exchange argument; refute by small counterexample.
Activity selection: earliest finish time. Fractional knapsack: by value per weight. Minimize max lateness: earliest deadline. Coin change {4,3,1} for 6: greedy 3 coins, optimal 2.
Huffman: merge two smallest (min-heap, O(n log n)); cost = Σ f·depth = sum of all internal-node frequencies. Prefix-free code = full binary tree.
MST: cut property (lightest crossing edge is safe); cycle property (unique heaviest edge on a cycle is in no MST). Distinct weights ⇒ unique MST. Tree on n nodes has n − 1 edges. Shortest-path tree ≠ MST in general.
Horn formula: set all false, set heads of unsatisfied implications true; then check pure negative clauses. Linear time.
Greedy set cover: at most \(k \ln n\) sets (approximation factor ln n), not optimal.

Dynamic programming (ch 6)

Needs optimal substructure + overlapping subproblems. Subproblems form a DAG; fill in topological order. Cost = #subproblems × work each.
LIS: L(j) ends at j; O(n²). Edit distance: E(i, j) on two prefixes, O(mn), reads up, left, diagonal; two rows suffice for the value. LCS: same shape.
Knapsack with repetition K(w), 0/1 K(w, j): both O(nW), pseudo-polynomial.
Chain matrix: intervals C(i, j), O(n³). p×q times q×r costs pqr.
Binomial \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) (Pascal), O(nk) table.
Weighted interval scheduling (sorted by finish): \(\text{OPT}(n) = \max\{\text{OPT}(n-1),\ w_n + \text{OPT}(p(s_n)-1)\}\), \(p(s_n)\) = first interval finishing after \(s_n\). Θ(n log n) with binary search.
Tree max independent set: in(u), out(u), O(n). Plain recursive Fibonacci: exponential calls; DP O(n) time, O(1) extra space.