Breadth-first search holds the search frontier in which data structure?

A priority queue ordered by a heuristic

The minimax algorithm assumes a game that is

two-player, zero-sum and deterministic, with perfect information

cooperative, with information hidden from both players

continuous-valued and infinite in depth

Alpha-beta pruning, compared with plain minimax search on the same game tree,

computes the identical minimax value while examining fewer nodes

computes a different, approximate value to save time

computes the identical minimax value while examining fewer nodes

only works for games with more than two players

requires no evaluation function at any leaf

Which of the following are true of propositional logic versus first-order (predicate) logic?

First-order logic adds quantifiers and predicates over objects that propositional logic lacks

Every propositional-logic sentence can be expressed as a special case of a first-order sentence

First-order logic is strictly more expressive than propositional logic

First-order logic adds quantifiers and predicates over objects that propositional logic lacks

Every propositional-logic sentence can be expressed as a special case of a first-order sentence

Propositional logic can express 'every student passed some exam' just as generally as first-order logic

First-order logic is strictly more expressive than propositional logic

A Bayesian network's directed acyclic graph structure primarily encodes

which conditional independence assumptions hold among the variables

the numerical value of every probability in the joint distribution

which conditional independence assumptions hold among the variables

the order in which variables were measured in an experiment

the total number of variables in the domain, and nothing else

Variable elimination's computational cost depends heavily on

the elimination order chosen for the variables

the alphabetical order of the variable names

the elimination order chosen for the variables

whether the network diagram is drawn left-to-right or top-to-bottom

the programming language used to implement the algorithm

Approximate inference through sampling becomes preferable to exact inference mainly when

exact inference such as variable elimination becomes too expensive on a large, densely connected network

the network has only two variables

exact inference such as variable elimination becomes too expensive on a large, densely connected network

the query variable has no parent nodes at all

all the evidence variables happen to be continuous

Using A* with graph search and a heuristic that is admissible but NOT consistent, the guarantee that can fail is that

a node, once expanded, may still need to be re-expanded after a cheaper path to it is found later

the algorithm no longer terminates at all

a node, once expanded, may still need to be re-expanded after a cheaper path to it is found later

the search no longer finds any solution whatsoever

admissibility itself silently stops holding partway through the search

Which of the following are true of minimax and alpha-beta pruning?

Minimax assumes optimal play from both players at every turn

Alpha-beta's best-case node reduction (to roughly b^(d/2)) assumes a well-ordered tree

Alpha-beta pruning still needs an evaluation function at cut-off depth, exactly as minimax does

Minimax assumes optimal play from both players at every turn

Alpha-beta pruning can arrive at a different final move than plain minimax on the same tree

Alpha-beta's best-case node reduction (to roughly b^(d/2)) assumes a well-ordered tree

Alpha-beta pruning still needs an evaluation function at cut-off depth, exactly as minimax does

A Bayesian network shaped as a tree, where every variable has at most one parent, allows exact inference such as variable elimination to run in time that is

linear in the number of variables

exponential in the number of variables regardless of the network's shape

linear in the number of variables

always slower than on a fully, densely connected network of the same size

undefined, because a tree-structured network cannot represent conditional independence

Artificial Intelligence

Section 7 of the GATE Data Science and Artificial Intelligence (DA) paper, and its last: search that finds a path or a move when the space of possibilities is too large to look at exhaustively — uninformed, informed and adversarial — logic that lets a fact be represented and a new one derived from it rather than merely stored, propositional and predicate, and reasoning under uncertainty, where conditional independence, exact inference through variable elimination and approximate inference through sampling turn a probability distribution too large to write out into one a machine can actually query.

1. Uninformed search: BFS, DFS, uniform-cost search

A search problem is defined by an initial state, the actions available in each state, a transition model saying what state an action leads to, a goal test, and a path cost. Uninformed (blind) search strategies use nothing but this definition — no estimate of how close a state is to the goal — and differ mainly in what data structure holds the frontier of states waiting to be expanded. Breadth-first search (BFS) uses a FIFO queue, is complete (it finds a goal if one exists, in a finite space) and optimal when every action costs the same, but its memory use grows exponentially with depth. Depth-first search (DFS) uses a stack (explicit, or via recursion), using memory only linear in the depth reached so far, but it is neither complete on an infinite-depth space without a depth limit nor optimal even when it does terminate.

⚠️ DFS's memory efficiency is not automatically an advantage

A common mistake is treating DFS as simply 'better' than BFS because it uses less memory. On an infinite or very deep state space with no depth limit, DFS can descend down one endless or very deep branch and never find a goal that sits just a few steps away down a different branch — its low memory footprint says nothing about whether it will actually terminate with an answer.

Uniform-cost search generalises BFS to graphs where actions cost different amounts: it always expands the frontier node with the lowest cumulative path cost so far, using a priority queue rather than a plain FIFO queue. This keeps optimality even when step costs differ, at the cost of needing to track and compare costs rather than simply counting edges — BFS's optimality guarantee is exactly the special case where every step cost is equal.

2. Informed search: heuristics, greedy best-first search, A*

A heuristic function h(n) estimates the cost from state n to the nearest goal, using domain knowledge that uninformed search ignores entirely. Greedy best-first search always expands the frontier node with the lowest h(n) — fast in practice, since it heads straight toward what looks like the goal, but not optimal (a low-h(n) path can still be a long or expensive one overall) and not complete without extra care against loops. A* search instead expands the node with the lowest f(n) = g(n) + h(n), the sum of the cost already paid and the estimated cost still to come, balancing 'how far I've come' against 'how far I have left'.

ℹ️ Admissibility gives optimality; consistency gives no re-expansion

A heuristic is admissible when it never overestimates the true cheapest cost to the goal, and this is exactly the condition that makes A* (using tree search) find an optimal solution. A heuristic is consistent (or monotonic) when, for every edge from n to a neighbour n', h(n) ≤ cost(n, n') + h(n') — a stronger condition that additionally guarantees A* (using graph search) never needs to re-expand a node once it has been expanded, because the path found to it the first time is already known to be the cheapest.

📖 A* was built to steer a real robot

A* was published in 1968 by Peter Hart, Nils Nilsson and Bertram Raphael at the Stanford Research Institute, as part of the software controlling Shakey — an early mobile robot that had to plan a route across a room of obstacles using whatever onboard computation it could afford. The algorithm's whole design goal was exactly the trade-off this section describes: use a heuristic to avoid uninformed search's blind exploration, but keep the guarantee of finding the shortest route rather than merely a fast-looking one.

3. Adversarial search: minimax and alpha-beta pruning

Minimax applies to a two-player, zero-sum, deterministic game of perfect information: it builds the game tree alternating a MAX player's turn and a MIN player's turn, assigns a value to each leaf (win/loss/draw, or a heuristic evaluation if the tree is cut off early), and backs those values up the tree — MAX picks the child of highest value at its turn, MIN the child of lowest value at its turn — so that the value at the root is the outcome both players get under the assumption that each plays optimally against the other.

Alpha-beta pruning explores the same game tree but cuts off any branch that provably cannot change the final decision, using two bounds carried down the search: α, the best value MAX can already guarantee, and β, the best value MIN can already guarantee. It computes exactly the same minimax value as full search while examining fewer nodes — in the best case, with a well-ordered tree, the effective branching factor is roughly halved, reducing the nodes examined from about bᵈ to about b^(d/2).

🎯 Alpha-beta pruning is an optimisation, not an approximation

It is worth stating precisely, because the word 'pruning' can suggest something is being given up: alpha-beta pruning never changes the final decision minimax would have reached with a full search. It only skips branches whose values are already provably irrelevant to that decision, given the bounds established so far — it is exactly minimax, computed faster, not a cheaper but riskier substitute for it.

4. Logic: propositional and predicate

Propositional logic builds sentences from atomic propositions (each either true or false) combined with the connectives ¬, ∧, ∨, → and ↔. For n distinct atoms, a truth table enumerates all 2ⁿ possible assignments, against which a sentence is satisfiable if at least one assignment makes it true, valid (a tautology) if every assignment makes it true, and unsatisfiable if no assignment makes it true. A knowledge base KB entails a sentence α (written KB ⊨ α) exactly when α is true in every model — every assignment — in which KB itself is true.

⚠️ Satisfiable and valid are not opposite ends of one scale

A sentence can be satisfiable without being valid — true in some models and false in others — which is the ordinary case for most sentences of interest, not an edge case. Valid means true in every model; unsatisfiable means false in every model; satisfiable only rules out the second of those, so 'satisfiable' and 'valid' are not each other's negation, and a sentence being satisfiable says nothing about whether it is also valid.

First-order (predicate) logic adds objects, predicates over those objects, functions and two quantifiers — ∀ (for all) and ∃ (there exists) — letting it state facts propositional logic has no general way to express, such as 'every student passed some exam': propositional logic has only fixed atomic facts with no notion of objects or variables ranging over them, so it can encode one specific instance of that sentence but not the general quantified statement itself. Every propositional sentence is expressible in first-order logic as the special case of a predicate with no arguments, but not every first-order sentence reduces to a propositional one — first-order logic is strictly the more expressive of the two.

5. Reasoning under uncertainty: conditional independence, variable elimination, sampling

X is conditionally independent of Y given Z when P(X | Y, Z) = P(X | Z) — knowing Y adds nothing once Z is already known. This is what lets a joint distribution over many variables be represented compactly instead of as one table with an entry for every combination of every variable's values, which grows exponentially with the number of variables. A Bayesian network represents these independencies directly, as a directed acyclic graph in which each node's distribution is conditioned only on its parents — the graph's structure is itself the statement of which conditional independencies the model assumes, not merely a picture drawn alongside it.

Exact inference by variable elimination answers a probabilistic query by eliminating the non-query, non-evidence variables one at a time in a chosen order: for each variable being eliminated, it multiplies together only the factors (conditional-probability tables) that mention it, and sums (marginalises) that variable out of the product — cheaper, in general, than building and summing the full joint distribution table directly, since it never materialises the whole joint at once.

⚠️ The elimination order decides variable elimination's cost, not just its correctness

Variable elimination gives the correct answer regardless of the order variables are eliminated in, but a badly chosen order can produce large intermediate factors over many variables at once, making the computation as expensive as building the full joint distribution it was meant to avoid — a well-chosen order, exploiting the network's actual structure, is what keeps the method's advantage real rather than theoretical.

When exact inference becomes too expensive — which it typically does on large, densely connected networks — approximate inference through sampling estimates the query instead: it draws many samples consistent with the network's distribution and computes the answer from their observed frequencies rather than computing it exactly. Its accuracy improves only in the limit of enough samples, and it trades a guarantee of exactness for the ability to scale to networks where exact methods are simply infeasible.

Key takeaways

BFS (FIFO queue) is complete and optimal with uniform step costs but exponential in memory; DFS (stack) is memory-linear but neither complete on an infinite space nor optimal; uniform-cost search generalises BFS's optimality to unequal step costs using a priority queue.
An admissible heuristic (never overestimates) makes A* optimal; a consistent heuristic additionally guarantees A* never re-expands a node — and greedy best-first search, using h(n) alone, is fast but neither guarantee applies to it.
Alpha-beta pruning computes the identical minimax value while examining fewer nodes — a well-ordered tree roughly halves the effective branching factor — and it never changes the final decision minimax would reach.
A sentence being satisfiable (true in some model) does not make it valid (true in every model); first-order logic strictly extends propositional logic with quantifiers and objects, so every propositional sentence is a special case of a predicate one but not the reverse.
Conditional independence is what a Bayesian network's graph structure directly encodes; variable elimination answers a query exactly by summing out variables one at a time in an order that decides its cost, and sampling trades that exactness for the ability to scale to networks exact methods cannot handle.

Practice questions (18)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

Breadth-first search holds the search frontier in which data structure?
1. A stack
2. A FIFO queue
3. A priority queue ordered by a heuristic
4. A hash table
Show answer
Answer: B — A FIFO queue
BFS expands frontier nodes in the order they were added, which is exactly what a FIFO queue gives — this is what makes it explore level by level.
Depth-first search on an infinite state space, run with no depth limit, is
1. complete and optimal
2. complete, but not optimal
3. neither complete nor optimal
4. optimal, but not complete
Show answer
Answer: C — neither complete nor optimal
DFS can descend forever down one infinite branch and never reach a goal that exists elsewhere, so it is not complete; even when it does terminate, it offers no guarantee of finding the shortest path.
Uniform-cost search always expands the frontier node with the lowest
1. heuristic estimate h(n)
2. cumulative path cost g(n) so far
3. depth in the search tree
4. branching factor at that node
Show answer
Answer: B — cumulative path cost g(n) so far
Uniform-cost search always expands by lowest g(n) using a priority queue, which is what keeps it optimal even when step costs are unequal.
A* search expands nodes in order of lowest
1. g(n) alone
2. h(n) alone
3. f(n) = g(n) + h(n)
4. the branching factor
Show answer
Answer: C — f(n) = g(n) + h(n)
A* balances the cost already paid, g(n), against the estimated remaining cost, h(n), by expanding lowest f(n) = g(n) + h(n) first.
A* search using tree search is guaranteed to find an optimal solution when its heuristic is
1. consistent
2. admissible
3. always exactly zero
4. greedy
Show answer
Answer: B — admissible
Admissibility — never overestimating the true remaining cost — is the condition that guarantees A*'s optimality under tree search; consistency is a stronger condition needed for graph search's re-expansion guarantee.
Greedy best-first search, unlike A*, expands nodes using
1. f(n) = g(n) + h(n)
2. h(n) alone
3. g(n) alone
4. a randomly chosen order
Show answer
Answer: B — h(n) alone
Greedy best-first search expands the node that looks closest to the goal by h(n) alone, ignoring the cost already paid to reach it — which is exactly why it can be fast but non-optimal.
The minimax algorithm assumes a game that is
1. single-player and stochastic
2. two-player, zero-sum and deterministic, with perfect information
3. cooperative, with information hidden from both players
4. continuous-valued and infinite in depth
Show answer
Answer: B — two-player, zero-sum and deterministic, with perfect information
Minimax is built for exactly this class of game: two opposing players, a zero-sum payoff, deterministic transitions, and full visibility of the state for both players.
Alpha-beta pruning, compared with plain minimax search on the same game tree,
1. computes a different, approximate value to save time
2. computes the identical minimax value while examining fewer nodes
3. only works for games with more than two players
4. requires no evaluation function at any leaf
Show answer
Answer: B — computes the identical minimax value while examining fewer nodes
Alpha-beta pruning skips only branches proven irrelevant to the final decision, so its result is always identical to full minimax search, just reached by examining fewer nodes.
With a well-ordered game tree, alpha-beta pruning reduces the effective number of nodes examined from about bᵈ to about
1. bᵈ / 2
2. b^(d/2)
3. log(bᵈ)
4. bᵈ − d
Show answer
Answer: B — b^(d/2)
A well-ordered tree lets alpha-beta pruning cut the effective branching factor roughly in half, so the node count falls from about bᵈ to about b^(d/2) — a very different reduction from an additive or logarithmic one.
A propositional-logic sentence that is true under every possible truth assignment is called
1. satisfiable only
2. valid (a tautology)
3. unsatisfiable
4. a contradiction
Show answer
Answer: B — valid (a tautology)
True in every model is exactly the definition of valid (a tautology); satisfiable only requires truth in at least one model, which is a weaker claim.
Which of the following are true of propositional logic versus first-order (predicate) logic?
1. First-order logic adds quantifiers and predicates over objects that propositional logic lacks
2. Every propositional-logic sentence can be expressed as a special case of a first-order sentence
3. Propositional logic can express 'every student passed some exam' just as generally as first-order logic
4. First-order logic is strictly more expressive than propositional logic
Show answer
Answer: A — First-order logic adds quantifiers and predicates over objects that propositional logic lacks; B — Every propositional-logic sentence can be expressed as a special case of a first-order sentence; D — First-order logic is strictly more expressive than propositional logic
Propositional logic has no objects or variables to quantify over, so it cannot state the general quantified fact — only first-order logic can, which is exactly why it is the strictly more expressive of the two.
A Bayesian network's directed acyclic graph structure primarily encodes
1. the numerical value of every probability in the joint distribution
2. which conditional independence assumptions hold among the variables
3. the order in which variables were measured in an experiment
4. the total number of variables in the domain, and nothing else
Show answer
Answer: B — which conditional independence assumptions hold among the variables
The graph's edges (each node depending only on its parents) are themselves the statement of which conditional independencies the model assumes; the numerical probabilities are stored separately, in each node's conditional probability table.
Exact inference by variable elimination answers a probabilistic query by
1. enumerating and summing the full joint distribution table directly
2. marginalizing out non-query, non-evidence variables one at a time, multiplying only the factors that mention each
3. drawing random samples from the network and counting their frequencies
4. ignoring the network's structure entirely and using only the prior
Show answer
Answer: B — marginalizing out non-query, non-evidence variables one at a time, multiplying only the factors that mention each
Variable elimination eliminates one variable at a time, multiplying only the factors that mention it and summing it out of that product — the sampling-based description in option 3 is what approximate inference does instead.
Variable elimination's computational cost depends heavily on
1. the alphabetical order of the variable names
2. the elimination order chosen for the variables
3. whether the network diagram is drawn left-to-right or top-to-bottom
4. the programming language used to implement the algorithm
Show answer
Answer: B — the elimination order chosen for the variables
A badly chosen elimination order can produce large intermediate factors, making the computation as expensive as the full joint distribution the method is meant to avoid.
Approximate inference through sampling becomes preferable to exact inference mainly when
1. the network has only two variables
2. exact inference such as variable elimination becomes too expensive on a large, densely connected network
3. the query variable has no parent nodes at all
4. all the evidence variables happen to be continuous
Show answer
Answer: B — exact inference such as variable elimination becomes too expensive on a large, densely connected network
Sampling trades away exactness for scalability, which is worthwhile exactly when exact methods become computationally infeasible on large, densely connected networks.
Using A* with graph search and a heuristic that is admissible but NOT consistent, the guarantee that can fail is that
1. the algorithm no longer terminates at all
2. a node, once expanded, may still need to be re-expanded after a cheaper path to it is found later
3. the search no longer finds any solution whatsoever
4. admissibility itself silently stops holding partway through the search
Show answer
Answer: B — a node, once expanded, may still need to be re-expanded after a cheaper path to it is found later
Admissibility alone still gives an optimal final answer, but without consistency graph search can find a cheaper path to an already-expanded node later on, forcing a re-expansion — consistency is exactly the stronger condition that rules this out.
Which of the following are true of minimax and alpha-beta pruning?
1. Minimax assumes optimal play from both players at every turn
2. Alpha-beta pruning can arrive at a different final move than plain minimax on the same tree
3. Alpha-beta's best-case node reduction (to roughly b^(d/2)) assumes a well-ordered tree
4. Alpha-beta pruning still needs an evaluation function at cut-off depth, exactly as minimax does
Show answer
Answer: A — Minimax assumes optimal play from both players at every turn; C — Alpha-beta's best-case node reduction (to roughly b^(d/2)) assumes a well-ordered tree; D — Alpha-beta pruning still needs an evaluation function at cut-off depth, exactly as minimax does
Alpha-beta pruning always reaches the identical decision as full minimax on the same tree — the second option is the false one; the other three are standard, correct properties of the two algorithms.
A Bayesian network shaped as a tree, where every variable has at most one parent, allows exact inference such as variable elimination to run in time that is
1. exponential in the number of variables regardless of the network's shape
2. linear in the number of variables
3. always slower than on a fully, densely connected network of the same size
4. undefined, because a tree-structured network cannot represent conditional independence
Show answer
Answer: B — linear in the number of variables
A tree-structured network's sparse, single-parent structure means variable elimination's intermediate factors stay small, giving linear-time inference — exactly the payoff of exploiting the network's actual structure that a badly ordered elimination on a dense network gives up.