CS3491 — Artificial Intelligence & Machine

Learning
Previous Year Question Paper — Model Answers
Units I & II | Anna University Regulation 2021 | Exam Preparation Guide

UNIT I — PROBLEM SOLVING

Reference: Russell & Norvig, 'Artificial Intelligence – A Modern Approach', 4th Ed., Pearson, 2021

Q: 1. Explain the A* Search Algorithm with an example. (16 Marks) [Nov/Dec 2023, Apr/May
2024]

A* Search Algorithm
A* is an informed (heuristic) best-first search algorithm that finds the shortest path from a start node
to a goal node. It uses both the actual cost to reach a node and an estimated cost to the goal.

Evaluation Function: f(n) = g(n) + h(n)

• g(n) = actual cost from start node to node n
• h(n) = heuristic estimate from n to goal (must be admissible, i.e., never overestimates)
• f(n) = estimated total cost of cheapest path through n

Admissibility Condition
A heuristic h(n) is admissible if: h(n) ≤ h*(n) for all nodes n, where h*(n) is the true cost.
A* is complete and optimal when h(n) is admissible.

Algorithm Steps
• 1. Initialize OPEN list with start node; CLOSED list is empty
• 2. If OPEN is empty → failure. Else pick node n with lowest f(n) from OPEN
• 3. If n is goal → return solution (trace back path)
• 4. Expand n: generate all successors
• 5. For each successor s: compute g(s) = g(n) + cost(n,s), compute f(s) = g(s) + h(s)
• 6. If s is in OPEN with lower f → skip. If s is in CLOSED with lower f → skip. Else add to
OPEN
• 7. Add n to CLOSED. Go to step 2

Example: Romania Map Problem (Russell & Norvig)

Goal: Arad → Bucharest. Heuristic h(n) = Straight-line distance to Bucharest (SLD).
Node g(n) h(n) SLD f(n)

Arad 0 366 366

Sibiu 140 253 393

 Rimnicu Vilcea 220 193 413

Fagaras 239 176 415

Pitesti 317 100 417

Bucharest (via Pitesti) 418 0 418

A* selects nodes in order of increasing f(n). It expands Arad → Sibiu → Rimnicu Vilcea → Pitesti →
Bucharest. Total cost = 418 km (optimal path).

Comparison: A* vs Other Searches

Property BFS Greedy Best-First A*

Complete? Yes No Yes

Optimal? Yes (unit cost) No Yes (admissible h)

Time O(b^d) O(b^m) O(b^d)

Space O(b^d) O(b^m) O(b^d)

Uses g(n)? Yes No Yes

Uses h(n)? No Yes Yes

📌 Note: A* is optimal if h(n) is admissible. Consistent heuristic (h(n) ≤ c(n,a,n') + h(n')) guarantees f is
non-decreasing along any path.

Q: 2. Explain Minimax Algorithm and Alpha-Beta Pruning with example. (16 Marks) [Apr/May
2023, Nov/Dec 2023, Apr/May 2024]

Adversarial Search — Game Playing

In adversarial search, two players (MAX and MIN) alternate moves. MAX tries to maximize the
score; MIN tries to minimize it. Minimax gives the optimal strategy for both players.

Minimax Algorithm
Minimax computes the minimax value of each node in the game tree.

• Terminal node: return utility value (e.g., +1 win, 0 draw, -1 loss)

• MAX node: return maximum of children's minimax values
• MIN node: return minimum of children's minimax values

Pseudocode
function MINIMAX-VALUE(state):
if TERMINAL(state): return UTILITY(state)
if MAX turn: return max(MINIMAX-VALUE(s) for s in SUCCESSORS(state))
if MIN turn: return min(MINIMAX-VALUE(s) for s in SUCCESSORS(state))

Example Game Tree

Consider MAX at root, MIN at level 1, terminal at level 2:
 Level Node Children Values Minimax Value

2 (Terminal) D 3, 5, 2 —

2 (Terminal) E 9, 1 —

2 (Terminal) F 4, 7 —

1 (MIN) B (parent of D,E) min(3,9) = ? 3

1 (MIN) C (parent of F) min(4) = ? 4

0 (MAX) A (parent of B,C) max(3,4) 4

Result: MAX picks C, which leads to utility 4. MIN plays optimally to minimize below that.

Alpha-Beta Pruning
Alpha-Beta pruning eliminates branches that cannot possibly affect the final decision, making
Minimax faster.

Alpha (α): Best value MAX can guarantee so far (initialize to -∞)
Beta (β): Best value MIN can guarantee so far (initialize to +∞)

Pruning Conditions
• At a MIN node: if value ≤ α → PRUNE (MAX would never choose this branch)
• At a MAX node: if value ≥ β → PRUNE (MIN would never choose this branch)

Alpha-Beta Example
Trace with α=-∞, β=+∞:
MAX(root) → MIN(B) → Terminal D1=3: α=3
MIN(B) → Terminal D2=5: min(3,5)=3, β=3 at B
→ return 3 to MAX; α=3
MAX(root) → MIN(C) → Terminal E1=2: min so far=2 < α=3 → PRUNE rest of C
→ Branch under C is pruned!
Final: MAX picks B, value = 3

Property Minimax Alpha-Beta Pruning

Time Complexity O(b^m) O(b^(m/2)) best case

Nodes evaluated All nodes ~Half (optimal ordering)

Result Same optimal Same optimal (no loss)

Space Complexity O(bm) O(bm)

📌 Note: Alpha-Beta does NOT change the result — it only speeds up Minimax. Best case: prunes half the
tree, equivalent to searching depth 2m in same time as m.

Q: 3. Explain BFS and DFS with their properties. Compare them. (16 Marks) [Apr/May 2023]

Breadth-First Search (BFS)

BFS explores all nodes at depth d before expanding nodes at depth d+1. It uses a FIFO queue.
BFS Algorithm
• 1. Initialize queue with start node
• 2. Dequeue front node; if goal → return success
• 3. Expand node, enqueue all unvisited successors
• 4. If queue empty → failure

Depth-First Search (DFS)

DFS explores as deep as possible before backtracking. It uses a LIFO stack (or recursion).

DFS Algorithm
• 1. Initialize stack with start node
• 2. Pop top node; if goal → return success
• 3. Expand node, push all unvisited successors
• 4. If stack empty → failure

Property BFS DFS

Data Structure Queue (FIFO) Stack (LIFO)

Complete? Yes (finite b) No (infinite depth)

Optimal? Yes (unit step cost) No

Time Complexity O(b^(d+1)) O(b^m)

Space Complexity O(b^(d+1)) O(bm)

When to use Shortest path, small depth Memory limited, deep

solutions

b = branching factor, d = depth of shallowest goal, m = maximum depth

📌 Note: Iterative Deepening Search (IDS) combines DFS space efficiency (O(bd)) with BFS
completeness and optimality. It is the preferred uninformed search.

Q: 4. Explain Constraint Satisfaction Problem (CSP) with example. (16 Marks) [Nov/Dec 2023]

Definition
A CSP is defined by:
• Variables: X = {X1, X2, ..., Xn}
• Domains: Di = set of possible values for Xi
• Constraints: C = set of conditions restricting variable values
A solution assigns a value to every variable satisfying all constraints.

Example: Map Coloring

Variables: WA, NT, SA, Q, NSW, V, T (Australian states). Domain: {Red, Green, Blue}
Constraints: Adjacent states must have different colors.
E.g., WA ≠ NT, WA ≠ SA, NT ≠ SA, NT ≠ Q, SA ≠ Q, SA ≠ NSW, SA ≠ V, Q ≠ NSW, NSW ≠ V

Backtracking Search for CSP

 function BACKTRACK(assignment, csp):
if assignment complete: return assignment
var = SELECT-UNASSIGNED-VARIABLE(csp)
for each value in DOMAIN(var):
if CONSISTENT(value, assignment):
add {var = value} to assignment
result = BACKTRACK(assignment, csp)
if result != failure: return result
remove {var = value} from assignment
return failure

Constraint Propagation — Arc Consistency (AC-3)

Arc (Xi, Xj) is arc-consistent if for every value in Di there is some value in Dj that satisfies the
constraint between Xi and Xj.
• AC-3 removes values from domains that cannot satisfy arcs
• Reduces domain size before/during search
• Time complexity: O(cd^3) where c = constraints, d = domain size

Heuristics for CSP

Heuristic Strategy Purpose

MRV Choose variable with fewest Fail early

legal values

Degree Choose variable with most Reduce future branching

constraints

LCV Choose value that rules out Leave options open

fewest neighbors

Q: 5. Solve the Water Jug Problem using State Space Search. (16 Marks) [Frequently Asked]

Problem Statement
Given: 4-gallon jug (J4) and 3-gallon jug (J3), no markings. Goal: Get exactly 2 gallons in J4.
State: (x, y) where x = gallons in J4, y = gallons in J3. Initial: (0,0) Goal: (2,0)

Operators / Rules
Rule Condition Action New State

1. Fill J4 x<4 Fill J4 from pump (4, y)

2. Fill J3 y<3 Fill J3 from pump (x, 3)

3. Empty J4 x>0 Pour J4 on ground (0, y)

4. Empty J3 y>0 Pour J3 on ground (x, 0)

5. Pour J4→J3 x>0, y<3 Pour x into J3 till full (x-(3-y), 3) or (0, y+x)

6. Pour J3→J4 y>0, x<4 Pour y into J4 till full (4, y-(4-x)) or (x+y, 0)

Solution Path
 Step Action State (J4, J3)

Start — (0, 0)

1 Fill J3 (0, 3)

2 Pour J3 → J4 (3, 0)

3 Fill J3 (3, 3)

4 Pour J3 → J4 (fill) (4, 2)

5 Empty J4 (0, 2)

6 Pour J3 → J4 (2, 0) ← GOAL!

📌 Note: The solution uses 6 steps. State space search systematically explores all states to find this path.

Q: 6. Explain Hill Climbing and Genetic Algorithm. (16 Marks) [Nov/Dec 2023, Apr/May 2024]

Hill Climbing Search

Hill climbing is a local search algorithm that continuously moves in the direction of increasing value
(gradient ascent). It doesn't maintain a search tree — only the current state.

Algorithm
function HILL-CLIMB(problem):
current = INITIAL-STATE
loop:
neighbor = highest-valued successor of current
if VALUE(neighbor) <= VALUE(current): return current
current = neighbor

Problems with Hill Climbing

Problem Description Solution

Local Maxima Peak not global optimum Random restart

Plateaus Flat region, no gradient Random sideways moves

Ridges Narrow peak hard to navigate Multiple simultaneous moves

Simulated Annealing
Escapes local maxima by occasionally accepting worse moves. Probability of accepting bad move =
e^(ΔE/T), where T is temperature (decreases over time). Based on annealing process in metallurgy.

Genetic Algorithm
Genetic algorithms (GAs) are inspired by biological evolution. They maintain a population of
candidate solutions and evolve them using selection, crossover, and mutation.

GA Components
• Population: Set of candidate solutions (chromosomes)
• Fitness Function: Evaluates quality of each individual
 • Selection: Choose parents — fitter individuals selected more often (roulette wheel,
tournament)
• Crossover (Recombination): Combine two parents to produce offspring
• Mutation: Randomly flip bits to maintain diversity
• Replacement: New population replaces old

GA for 8-Queens Problem

Chromosome: Sequence of 8 digits, each 1–8, representing queen column position per row.
Fitness: Number of non-attacking pairs (max = 28 for 8 queens).
Example:
Individual Chromosome Fitness (non-attacks)

P1 32748552 24

P2 24748552 23

Crossover at pos 5 32748 | 552 + 247 | 48552 —

Offspring 32748552 or mutation 25 (improved)

UNIT II — PROBABILISTIC REASONING
Reference: Russell & Norvig, 'Artificial Intelligence – A Modern Approach', 4th Ed., Chapters 12–13

Q: 1. Explain Bayesian Networks with structure and inference. (16 Marks) [Apr/May 2023,
Nov/Dec 2023, Apr/May 2024]

Definition
A Bayesian Network (BN) is a Directed Acyclic Graph (DAG) representing the joint probability
distribution of a set of random variables. Each node represents a variable; edges represent direct
dependencies.

Components
• Nodes: Random variables (discrete or continuous)
• Directed Edges: X → Y means X is a direct cause/influence of Y
• Conditional Probability Table (CPT): Each node Xi has a CPT: P(Xi | Parents(Xi))

Joint Probability Factorization

P(X1, X2, ..., Xn) = Π P(Xi | Parents(Xi))
This product form exploits conditional independence, making representation compact.

Classic Example: Burglary-Alarm Network

Variables: Burglary (B), Earthquake (E), Alarm (A), JohnCalls (J), MaryCalls (M)
Structure: B → A ← E, A → J, A → M

Node Parents CPT values

B (Burglary) None P(B) = 0.001

E (Earthquake) None P(E) = 0.002

A (Alarm) B, E P(A|B,E)=0.95, P(A|

B,¬E)=0.94, P(A|¬B,E)=0.29,
P(A|¬B,¬E)=0.001

J (JohnCalls) A P(J|A)=0.90, P(J|¬A)=0.05

M (MaryCalls) A P(M|A)=0.70, P(M|¬A)=0.01

Worked Example — Computing Joint Probability

P(B=T, E=F, A=T, J=T, M=T) = P(B)·P(E=F)·P(A|B,E=F)·P(J|A)·P(M|A)
= 0.001 × 0.998 × 0.94 × 0.90 × 0.70
= 0.001 × 0.998 × 0.94 × 0.63 ≈ 0.000592

Exact Inference — Enumeration

Query: P(B | J=T, M=T) — what is probability of burglary given both called?
 P(B=T | J=T, M=T) ∝ Σ_e Σ_a P(B=T)·P(e)·P(a|B=T,e)·P(J=T|a)·P(M=T|a)
Normalize to get: P(B=T | J=T, M=T) ≈ 0.284

Approximate Inference
Method Strategy Use Case

Rejection Sampling Sample from prior, reject if Simple, low accuracy

inconsistent with evidence

Likelihood Weighting Fix evidence, weight samples More efficient than rejection
by P(evidence)

MCMC / Gibbs Sampling Markov chain — resample Large complex networks

each variable given its Markov
blanket

📌 Note: Markov Blanket of node X = Parents(X) + Children(X) + Co-parents. X is conditionally

independent of all other nodes given its Markov Blanket.

Q: 2. Explain Naive Bayes Classifier with example. (16 Marks) [Apr/May 2023, Nov/Dec 2023]

Definition
Naive Bayes is a probabilistic classifier based on Bayes' theorem with a strong (naive) assumption
of conditional independence among features given the class.

Bayes' Theorem
P(C | x1, x2, ..., xn) = [ P(C) × P(x1,x2,...,xn | C) ] / P(x1,x2,...,xn)

Naive Assumption
Features are conditionally independent given class C:
P(x1, x2, ..., xn | C) = P(x1|C) × P(x2|C) × ... × P(xn|C)

Classification Rule
Predicted Class = argmax_C [ P(C) × Π P(xi | C) ]
We ignore the denominator P(x) since it is constant for all classes.

Worked Example: Spam Email Classification

Training data: 10 emails — 6 spam, 4 not spam.
Features: words 'free', 'money', 'hello'
Feature P(word|Spam) P(word|NotSpam)

free 4/6 = 0.67 1/4 = 0.25

money 3/6 = 0.50 1/4 = 0.25

hello 1/6 = 0.17 3/4 = 0.75

New email contains: 'free', 'money'. Classify:

P(Spam) = 6/10 = 0.6, P(NotSpam) = 4/10 = 0.4
P(Spam | free, money) ∝ 0.6 × 0.67 × 0.50 = 0.201
P(NotSpam | free, money) ∝ 0.4 × 0.25 × 0.25 = 0.025

Since 0.201 > 0.025 → Classified as SPAM

Laplace Smoothing
Problem: If P(xi|C) = 0 for any feature, the whole product becomes 0.
Solution: Add 1 to all counts (add-1 / Laplace smoothing):
P(xi|C) = (count(xi, C) + 1) / (count(C) + |Vocabulary|)

Types of Naive Bayes

Type Distribution Use Case

Gaussian NB Gaussian (Normal) Continuous features

Multinomial NB Multinomial Word counts (text

classification)

Bernoulli NB Bernoulli (0/1) Binary features (word

presence)

📌 Note: Despite the 'naive' independence assumption, Naive Bayes often performs surprisingly well in
practice, especially for text classification and spam filtering.

Q: 3. Explain Bayesian Inference and Acting Under Uncertainty. (16 Marks) [Apr/May 2024]

Why Uncertainty?
In real-world AI, agents cannot observe the world completely. Causes of uncertainty:
• Partial observability — cannot see all of state
• Noisy sensors — sensor readings are imperfect
• Non-deterministic actions — outcomes may vary
• Limited computation — cannot model everything

Probability Basics
Concept Formula / Meaning

Prior P(A) Probability of A before any evidence

Conditional P(A|B) Probability of A given B is observed

Joint P(A,B) P(A|B) × P(B) = P(B|A) × P(A)

Marginal P(A) ΣB P(A,B) — sum over all values of B

Bayes' Theorem P(A|B) = P(B|A)·P(A) / P(B)

Full Bayesian Inference

Given evidence e, compute posterior distribution over query variable X:
P(X | e) = α × P(X, e) = α × Σ_y P(X, e, y)
where α is a normalizing constant ensuring probabilities sum to 1.

Worked Example
Problem: A patient tests positive for a disease. Test has 99% accuracy. Disease prevalence = 1%.
Variables: D = has disease, T = tests positive

Given: P(D=T) = 0.01, P(T=+|D=T) = 0.99, P(T=+|D=F) = 0.01 (false positive rate)

Compute: P(D=T | T=+)

P(T=+) = P(T=+|D=T)·P(D=T) + P(T=+|D=F)·P(D=F)
= 0.99 × 0.01 + 0.01 × 0.99 = 0.0099 + 0.0099 = 0.0198

P(D=T | T=+) = P(T=+|D=T)·P(D=T) / P(T=+)

= (0.99 × 0.01) / 0.0198 = 0.0099 / 0.0198 = 0.5

Interpretation: Even with 99% accurate test and positive result, only 50% chance of having the
disease (base rate is very low). This demonstrates the importance of Bayesian reasoning.

Causal Networks
Causal networks (Pearl's do-calculus) distinguish between observing and intervening:
• Observation: P(Y | X=x) — conditioning on X
• Intervention: P(Y | do(X=x)) — setting X by intervention (ignores X's parents)
Example: Seeing someone carry an umbrella suggests it will rain [observation]. Making someone
carry an umbrella does NOT cause rain [intervention].

Q: 4. Explain Exact and Approximate Inference in Bayesian Networks. (16 Marks) [Nov/Dec
2023]

Exact Inference Methods

1. Enumeration
Compute query by summing over all combinations of hidden variables:
P(X | e) = α Σ_y P(X, e, y)
Limitation: Exponential time O(d^n) where n = variables, d = domain size.

2. Variable Elimination
Improves enumeration by eliminating hidden variables one at a time using factor multiplication and
marginalization.
Factors: f1=P(B), f2=P(E), f3=P(A|B,E), f4=P(J|A), f5=P(M|A)
Query: P(B|J=T, M=T)
Step 1: Set J=T, M=T → fix f4, f5
Step 2: Sum out E: f_AE(A,B) = Σ_E f2(E)·f3(A,B,E)
Step 3: Sum out A: f_B(B) = Σ_A f_AE(A,B)·f4(J=T|A)·f5(M=T|A)
Step 4: Normalize: P(B|J,M) = α·f1(B)·f_B(B)

Approximate Inference Methods

1. Rejection Sampling
• Generate N samples from the prior distribution P(X1,...,Xn)
• Reject samples inconsistent with evidence e
• Use remaining samples to estimate query
• Problem: Rejecting too many samples when evidence is unlikely

2. Likelihood Weighting
• Fix evidence variables to their observed values
• Sample only non-evidence variables from their conditional distributions
• Weight each sample by P(evidence | parents of evidence variables)
• More efficient than rejection sampling

3. Markov Chain Monte Carlo (MCMC) — Gibbs Sampling

• Start with any complete assignment consistent with evidence
• Repeatedly: pick a non-evidence variable Xi at random
• Sample Xi from P(Xi | Markov Blanket of Xi)
• Record sample; iterate many times
• Sample frequencies approximate the posterior

Method Accuracy Efficiency Handles large

networks?

Enumeration Exact Very slow No

Variable Elimination Exact Moderate Moderate

Rejection Sampling Approximate Poor (unlikely Yes

evidence)

Likelihood Weighting Approximate Good Yes

Gibbs Sampling Approximate Very good Yes

(MCMC)

2-MARK QUICK REFERENCE — UNITS I & II

Question Answer (1-2 sentences)

What is AI? The study and design of intelligent agents that

perceive environment and take actions to
maximize goal achievement.

Define rational agent. An agent that selects actions expected to

maximize its performance measure based on
percept sequence and built-in knowledge.

What is state space? The set of all states reachable from the initial
state by any sequence of actions.

Define admissible heuristic. A heuristic h(n) is admissible if it never

 overestimates the true cost: h(n) ≤ h*(n).

What is alpha-beta pruning? An optimization of minimax that prunes

branches that cannot affect the final decision,
using alpha (MAX bound) and beta (MIN
bound).

What is a CSP? A problem defined by variables, domains, and

constraints. Solution must satisfy all
constraints.

Define arc consistency. Arc (Xi,Xj) is arc-consistent if every value in Di

has at least one compatible value in Dj
satisfying the constraint.

What is Bayes' theorem? P(A|B) = P(B|A)·P(A) / P(B). Relates posterior,

likelihood, prior, and marginal likelihood.

What is a Bayesian Network? A DAG of random variables with CPTs

representing conditional dependencies for
compact joint probability representation.

What is Markov Blanket? The Markov blanket of X consists of its parents,

children, and co-parents. X is conditionally
independent of all others given its Markov
blanket.

What is Naive Bayes assumption? Features are conditionally independent given

the class: P(x1..xn|C) = ∏P(xi|C).

What is Laplace smoothing? Add 1 to all counts to avoid zero probability:

P(xi|C) = (count+1)/(total+|V|).

What is exact vs approximate inference? Exact: variable elimination (correct but slow).
Approximate: sampling methods (MCMC, LW)
— faster but not exact.

What is causal network? A network distinguishing intervention do(X=x)

from observation P(Y|X=x). Intervention
removes X's parents.

Define Hill Climbing. A local search that moves to the best

neighboring state; problem: may get stuck at
local maxima.

What is AO* algorithm? An extension of A* for AND-OR graphs used in

game trees and planning problems with
subgoals.

End of Document — Units I & II | CS3491 AIML | Anna University Reg 2021