Question & Answer Series

Artificial Intelligence (CS F407)

BITS Pilani K K Birla Goa Campus

BITS Pilani K K Birla Goa Campus

November 16, 2025

CS F407 (BITS Goa) QA slides November 16, 2025 1/9

Q1: 8-puzzle transition & path cost

Consider the 8-puzzle state (blank = ):

2 8 3
1 6 4
7  5

(a) Apply action Left (move the blank left) and then Up. Write the
resulting state.
(b) If each step costs 1, what is the path cost g of the two-step sequence?

CS F407 (BITS Goa) QA slides November 16, 2025 2/9

Q1: 8-puzzle transition & path cost

Solution. (a) After Left:

2 8 3
1 6 4
 7 5
Then Up:
2 8 3
 6 4
1 7 5
(b) Each move costs 1, so g = 2.

CS F407 (BITS Goa) QA slides November 16, 2025 2/9

Q2: Breadth-first search counts

Breadth-first search (BFS) with branching factor b = 3 finds the shallowest

goal at depth d = 4.
(a) How many nodes are generated in total (including the root)?
(b) What is the size of the explored set (expanded nodes) and the frontier
at the time just before the goal at depth 4 is selected?
(c) What is the space complexity in big-O in terms of b and d?

CS F407 (BITS Goa) QA slides November 16, 2025 3/9

Q2: Breadth-first search counts

Solution. (a) Total generated

= 1 + b + b 2 + b 3 + b 4P= 1 + 3 + 9 + 27 + 81 = 121.
(b) Explored set size = d−1 i
i=0 b = 1 + 3 + 9 + 27 = 40; frontier size
= b d = 81.
(c) Space is dominated by the frontier: O(b d ).

CS F407 (BITS Goa) QA slides November 16, 2025 3/9

Q3: When is Uniform-Cost Search optimal?

State the conditions under which Uniform-Cost Search (graph search) is

complete and cost-optimal. Also, when should the goal test be applied to
ensure optimality?

CS F407 (BITS Goa) QA slides November 16, 2025 4/9

Q3: When is Uniform-Cost Search optimal?

Solution. UCS is complete and cost-optimal if all step costs are positive
(bounded below by  > 0). The goal test must be applied when a node is
popped from the priority queue (i.e., when its current path cost is
minimum among the frontier). Under these conditions, the first time the
goal is removed from the queue, UCS has found an optimal-cost solution.

CS F407 (BITS Goa) QA slides November 16, 2025 4/9

Q4: Depth-Limited vs Iterative Deepening

Compare Depth-Limited Search (DLS) with limit ` and Iterative Deepening

Search (IDS) for a finite tree with uniform step cost 1 and shallowest goal
at depth d.
(a) For which settings are they complete?
(b) Which is optimal?
(c) Give their time and space complexities (big-O).

CS F407 (BITS Goa) QA slides November 16, 2025 5/9

Q4: Depth-Limited vs Iterative Deepening

Solution. (a) DLS is complete if ` ≥ d and there are no infinite-depth

paths within the limit; otherwise it can miss the goal. IDS is complete for
finite branching factor b.
(b) With unit step costs, IDS is optimal (finds the shallowest goal). DLS is
not guaranteed optimal.
(c) IDS runs in O(b d ) time and O(bd) space. DLS uses O(b ` ) time and
O(b`) space.

CS F407 (BITS Goa) QA slides November 16, 2025 5/9

Q5: Consistency check (triangle inequality)

For successive nodes n → n0 with step cost c(n, a, n0 ) = 2, suppose

h(n) = 5 and h(n0 ) = 2.
(a) Does this satisfy the consistency condition h(n) ≤ c(n, a, n0 ) + h(n0 )?
(b) What does consistency imply about the monotonicity of
f (n) = g (n) + h(n) along any path in A*?

CS F407 (BITS Goa) QA slides November 16, 2025 6/9

Q5: Consistency check (triangle inequality)

Solution. (a) Check: 5 ≤ 2 + 2 = 4 is false; the heuristic is inconsistent.

(b) If a heuristic is consistent, then f -values are nondecreasing along paths:
for any successor n0 , f (n0 ) ≥ f (n). Inconsistency can cause f to drop,
leading to re-expansions in graph search.

CS F407 (BITS Goa) QA slides November 16, 2025 6/9

Q6: Heuristic domination on the 8-puzzle

Let h1 be “number of misplaced tiles” and h2 be the “Manhattan distance.”

(a) Which heuristic dominates, and why?
(b) Which heuristic typically expands fewer nodes in A* (graph search),
and why?

CS F407 (BITS Goa) QA slides November 16, 2025 7/9

Q6: Heuristic domination on the 8-puzzle

Solution. (a) h2 dominates h1 because for every state n, h2 (n) ≥ h1 (n):

each misplaced tile contributes at least 1 unit of Manhattan distance.
(b) With the same tie-breaking, A* with h2 usually expands fewer nodes
since larger (still admissible/consistent) h tightens g (n) ≤ C ∗ − h(n),
shrinking the set {n | f (n) ≤ C ∗ }.

CS F407 (BITS Goa) QA slides November 16, 2025 7/9

Q7: Estimating effective branching factor b ∗

A search finds a solution at depth d = 5 after generating N = 363 nodes

(including the root). Using

N + 1 = 1 + b ∗ + (b ∗ )2 + · · · + (b ∗ )d ,

estimate b ∗ .

CS F407 (BITS Goa) QA slides November 16, 2025 8/9

Q7: Estimating effective branching factor b ∗

Solution. Compute N + 1 = 364. Test b ∗ = 3:

1 + 3 + 9 + 27 + 81 + 243 = 364 (exact match). Hence b ∗ ≈ 3.

CS F407 (BITS Goa) QA slides November 16, 2025 8/9

Q8: When is A* (graph) optimal?

State sufficient conditions under which A* graph search returns an optimal

solution. Also, what can be said about g (n) when a node n is popped from
the priority queue under those conditions?

CS F407 (BITS Goa) QA slides November 16, 2025 9/9

Q8: When is A* (graph) optimal?

Solution. With nonnegative step costs and a consistent heuristic, A*

graph search is complete and returns an optimal solution. Under
consistency, when a node n is popped, its current g (n) is the minimum-cost
path to n; in particular, when the goal is popped, the path found is optimal.

CS F407 (BITS Goa) QA slides November 16, 2025 9/9

 Question & Answer Series — CSP Practice
(Intermediate)

Artificial Intelligence (CS F407)

BITS Pilani K K Birla Goa Campus

BITS Pilani K K Birla Goa Campus

November 16, 2025

CS F407 (BITS Goa) QA slides November 16, 2025 1/5

Q1: Model a CSP and identify constraint types

Australian Map Coloring. Let variables be

X = {WA, NT , Q, NSW , V , SA, T } with a common domain
D = {red, green, blue}.
(a) Write three binary constraints that involve SA.
(b) Give one unary constraint and one global (Alldiff) constraint that could
appear in this domain.
(c) For the partial assignment A = {SA = red, WA = green}, is A
consistent? Briefly justify.

CS F407 (BITS Goa) QA slides November 16, 2025 2/5

Q1: Model a CSP and identify constraint types

Solution. (a) Examples: (SA 6= WA), (SA 6= NT ), (SA 6= V ). (Any three

neighbors of SA.)
(b) Unary example: WA 6= green. Global example:
Alldiff(WA, NT , Q, NSW , V , SA, T ).
(c) Yes, A is locally consistent w.r.t. the binary constraints used so far,
because none of the listed constraints is violated by SA = red and
WA = green (they only require SA 6= WA, which holds).

CS F407 (BITS Goa) QA slides November 16, 2025 2/5

Q2: One AC-3 pass and complexity

Consider variables X = {A, B, C } with domains

D(A) = {1, 2}, D(B) = {1, 2, 3}, D(C ) = {2, 3}.
Binary constraints: A 6= B, B 6= C .
(a) Run one AC-3 queue cycle starting from arcs
hA, Bi, hB, Ai, hB, C i, hC , Bi. Write the domains after this cycle stabilizes.
(b) State the worst-case time complexity of AC-3 in terms of number of
binary constraints c and max domain size d.

CS F407 (BITS Goa) QA slides November 16, 2025 3/5

Q2: One AC-3 pass and complexity

Solution. (a) Check REVISE(A, B) under A 6= B: every a ∈ D(A) has a

supporting b ∈ D(B) with a 6= b (e.g., 1 is supported by 2, 2 by 1), so
D(A) unchanged.
REVISE(B, A): each b ∈ D(B) must have a ∈ D(A) with b 6= a. For
b = 1 there is a = 2; for b = 2 there is a = 1; for b = 3 there is a ∈ {1, 2},
so no deletion.
REVISE(B, C ) under B 6= C : b = 2 has support c = 3; b = 3 has support
c = 2; b = 1 has support c ∈ {2, 3}, so unchanged.
REVISE(C , B): c = 2 has supporting b ∈ {1, 3}; c = 3 has supporting
b ∈ {1, 2}. No deletions.
Thus domains remain D(A) = {1, 2}, D(B) = {1, 2, 3}, D(C ) = {2, 3}.
(b) O(c d 3 ).

CS F407 (BITS Goa) QA slides November 16, 2025 3/5

Q4: One step of Min-Conflicts (8-Queens)

8-Queens in column representation: (r1 , . . . , r8 ) gives the row of the queen

in each column.
Current assignment: (1, 5, 8, 6, 3, 1, 7, 2). Conflicts are pairs of queens
sharing a row or diagonal.
(a) Pick a conflicted column (say the leftmost with a conflict). Identify
that column.
(b) For that column, evaluate conflicts for each possible row (1–8) and
choose the min-conflicts move. Write the new assignment after moving
just that queen. (Break ties by choosing the lowest-index row.)

CS F407 (BITS Goa) QA slides November 16, 2025 4/5

Q4: One step of Min-Conflicts (8-Queens)

Solution. Compute conflicts per column. Queens are at:

(1, 1), (2, 5), (3, 8), (4, 6), (5, 3), (6, 1), (7, 7), (8, 2).
Conflicts: Column 1 at (1, 1) conflicts with (6, 1) (same row) and with
(2, 5) (diag ∆r = ∆c = 4) and (4, 6) (diag 5). Thus column 1 is
conflicted; pick it.
Evaluate placing column 1 in each row r ∈ {1, . . . , 8} by counting attacks
with fixed others:
r conflicts
1 3 (as above)
2 attacks (8, 2) ⇒ 1
3 attacks (5, 3) ⇒ 1
4 attacks (2, 5), (7, 7) ⇒ 2
5 attacks (2, 5) ⇒ 1
6 attacks (4, 6) ⇒ 1
7 attacks (3, 8) ⇒ 1
8 no attack ⇒ 0
CS F407 (BITS Goa) QA slides November 16, 2025 4/5
Question & Answer Series — Chapter 7 (Logical Agents)

Artificial Intelligence (CS F407)

BITS Pilani K K Birla Goa Campus

BITS Pilani K K Birla Goa Campus

November 16, 2025

CS F407 (BITS Goa) QA slides November 16, 2025 1/5

Q1: Does the KB entail a ∧ c?

Given the propositional KB

ϕ ≡ (a ∨ b) ∧ (b ∨ c) ∧ (¬b).

Does ϕ |= (a ∧ c) hold? Justify briefly using either (i) model reasoning or

(ii) simple propositional inference.

CS F407 (BITS Goa) QA slides November 16, 2025 2/5

Q1: Does the KB entail a ∧ c?

Solution. Using inference with ¬b:

(a ∨ b) ∧ ¬b ⇒ a, (b ∨ c) ∧ ¬b ⇒ c.

Hence ϕ |= a ∧ c.
Model view: every model of ϕ must set b = F , forcing a = T from (a ∨ b)
and c = T from (b ∨ c). Therefore M(ϕ) ⊆ M(a ∧ c).

CS F407 (BITS Goa) QA slides November 16, 2025 2/5

Q4: Forward chaining on a Horn knowledge base

Horn KB (all implications are definite clauses):

F1: p F2: q
R1: q ⇒ r R2: (p ∧ r ) ⇒ s R3: s ⇒ t

Use forward chaining to determine whether t is entailed. List the sequence

of newly inferred atoms.

CS F407 (BITS Goa) QA slides November 16, 2025 3/5

Q4: Forward chaining on a Horn knowledge base

Solution. Start with facts {p, q}.

From R1, q ⇒ r : infer r . Now have {p, q, r }.
From R2, p ∧ r ⇒ s: infer s. Now {p, q, r , s}.
From R3, s ⇒ t: infer t.
Thus KB |= t. Sequence: r → s → t.

CS F407 (BITS Goa) QA slides November 16, 2025 3/5

 Question & Answer Series — Lecture 07 Practice
(Intermediate)

Artificial Intelligence (CS F407)

BITS Pilani K K Birla Goa Campus

BITS Pilani K K Birla Goa Campus

November 16, 2025

CS F407 (BITS Goa) QA slides November 16, 2025 1/6

Q1: Translate to FOL and check a consequence

English. “Every student who submits the assignment passes. Ajay is a

student and Ajay submitted the assignment.”
(a) Translate to FOL using predicates Student(x), Submitted(x),
Passed(x).
(b) Does the KB entail Passed(ajay)? Give a brief justification
(model-based or rule-based).

CS F407 (BITS Goa) QA slides November 16, 2025 2/6

Q1: Translate to FOL and check a consequence

Solution. (a) ∀x [Student(x) ∧ Submitted(x) ⇒

Passed(x)] ∧ Student(ajay ) ∧ Submitted(ajay ).
(b) By universal instantiation with x := ajay , we obtain
Student(ajay ) ∧ Submitted(ajay ) ⇒ Passed(ajay ). Given Student(ajay )
and Submitted(ajay ), modus ponens yields Passed(ajay ). Hence
KB |= Passed(ajay ).

CS F407 (BITS Goa) QA slides November 16, 2025 2/6

Q2: Forward chaining with an existential fact

KB.

R1: ∀x∀y TA(x, y ) ⇒ Employee(x)
E1: ∃y TA(Ajay , y )
Goal: Employee(Ajay ).
Run forward chaining; if needed, use Existential Instantiation (EI). Show
the derived ground facts.

CS F407 (BITS Goa) QA slides November 16, 2025 3/6

Q2: Forward chaining with an existential fact

Solution. Apply EI to E1 introducing a fresh constant c: assert

TA(Ajay , c).
Match R1 antecedent TA(x, y ) with TA(Ajay , c) using θ = {x/Ajay , y /c}.
Fire R1θ to add Employee(Ajay ). The goal appears in the fact set, so
forward chaining succeeds.

CS F407 (BITS Goa) QA slides November 16, 2025 3/6

Q3: Backward chaining over two rules

KB.

R1: ∀x Mammal(x) ⇒ WarmBlooded(x)


R2: ∀x Dog (x) ⇒ Mammal(x)
F1: Dog (fido)
Query: WarmBlooded(fido).
Show the sequence of subgoals selected and how they are discharged.

CS F407 (BITS Goa) QA slides November 16, 2025 4/6

Q3: Backward chaining over two rules

Solution. Start with goal G1 := WarmBlooded(fido).

Pick R1 (head unifies with G1 via {x/fido}); new subgoal
G2 := Mammal(fido).
Pick R2 (head unifies with G2 via {x/fido}); new subgoal G3 := Dog (fido).
G3 is a fact by F1 ⇒ G2 proved ⇒ G1 proved. Therefore
KB |= WarmBlooded(fido).

CS F407 (BITS Goa) QA slides November 16, 2025 4/6

Q4: Apply Generalized Modus Ponens (unification)

Rules and facts.

R: ∀x∀y Knows(x, y ) ∧ Helps(y , z) ⇒ Trusts(x, z)
F1: Knows(john, alice) F2: Helps(alice, bob)

Use unification and GMP to derive a ground consequence.

CS F407 (BITS Goa) QA slides November 16, 2025 5/6

Q4: Apply Generalized Modus Ponens (unification)

Solution. Unify Knows(x, y ) with Knows(john, alice) giving

{x/john, y /alice}.
Unify Helps(y , z) with Helps(alice, bob) extending the substitution to
{x/john, y /alice, z/bob}.
Fire R under this substitution to conclude Trusts(john, bob).

CS F407 (BITS Goa) QA slides November 16, 2025 5/6

Q5: Fuzzy rule evaluation and quick defuzzification

Fan control. Inputs: Temperature T = 32◦ C, Humidity H = 70%.

Memberships: µHighTemp (32) = 0.7, µMedTemp (32) = 0.4;
µHighHum (70) = 1.0, µMedHum (70) = 0.5.
Rules (Mamdani, AND via min):
R1: IF Temp High AND Hum High THEN Fan Fast. R2: IF Temp Med
AND Hum Med THEN Fan Medium.
Use representative centroids cMed = 60, cFast = 80 (on 0–100 scale).
(a) Compute firing strengths α1 , α2 . (b) Give a quick crisp speed by
weighted average of representatives.

CS F407 (BITS Goa) QA slides November 16, 2025 6/6

Q5: Fuzzy rule evaluation and quick defuzzification

Solution. (a) α1 = min(0.7, 1.0) = 0.7, α2 = min(0.4, 0.5) = 0.4.

(b) Quick estimate (weighted reps):

α2 cMed + α1 cFast 0.4 · 60 + 0.7 · 80 24 + 56

Speed ≈ = = ≈ 72.7.
α2 + α1 1.1 1.1
So the controller would select a “fast” setting (≈ 73%).

CS F407 (BITS Goa) QA slides November 16, 2025 6/6

 Question & Answer Series

Artificial Intelligence (IS ZC444)

BITS Pilani K. K. Birla Goa Campus

BITS Pilani K. K. Birla Goa Campus

November 23, 2025

IS ZC444 (BITS Goa) QA slides November 23, 2025 1 / 25

Q1: Full Joint — Simple Marginals and a Conditional

Use the full joint table for T (toothache), K (catch), C (cavity):

CTK : 0.108, CT ¬K : 0.012, C ¬TK : 0.072, C ¬T ¬K : 0.008,

¬CTK : 0.016, ¬CT ¬K : 0.064, ¬C ¬TK : 0.144, ¬C ¬T ¬K : 0.576

Tasks.
1 Compute P(C ) and P(T ).
2 Compute P(C | T ).

IS ZC444 (BITS Goa) QA slides November 23, 2025 2 / 25

Q1: Full Joint — Simple Marginals and a Conditional

Solution. Solutions.
1 P(C ) = 0.108 + 0.012 + 0.072 + 0.008 = 0.200 ;
P(T ) = 0.108 + 0.012 + 0.016 + 0.064 = 0.200 .
0.108 + 0.012
2 P(C | T ) = = 0.60 .
0.200

IS ZC444 (BITS Goa) QA slides November 23, 2025 2 / 25

Q2: BN Chain Rule — One Joint Term in the Alarm
Network
Alarm BN variables: B (Burglary), E (Earthquake), A (Alarm), J
(JohnCalls), M (MaryCalls).
CPT entries (time-invariant):

P(B=t) = 0.001, P(E =t) = 0.002,

P(A=t | B, E ) = {.95, .94, .29, .001} for (B, E ) = (t, t), (t, f ), (f , t), (f , f ),
P(J=t | A) = 0.90, P(J=t | ¬A) = 0.05,
P(M=t | A) = 0.70, P(M=t | ¬A) = 0.01.

Task. Using the BN factorization, compute P(¬J, M, A, ¬B, ¬E ).

IS ZC444 (BITS Goa) QA slides November 23, 2025 3 / 25

Q2: BN Chain Rule — One Joint Term in the Alarm
Network
Solution. By the BN chain rule:

P(¬J, M, A, ¬B, ¬E ) = P(¬J | A) P(M | A) P(A | ¬B, ¬E ) P(¬B) P(¬E ).

Numerically:

(0.10) × (0.70) × (0.001) × (0.999) × (0.998) ≈ 6.979 × 10−5 .

IS ZC444 (BITS Goa) QA slides November 23, 2025 3 / 25

Q3: Sprinkler Network — A Conditional from Given Joint
Terms
Cloudy–Sprinkler–Rain–WetGrass BN. You are given:

P(S=t, W =t) = 0.2781, P(S=f , W =t) = 0.369.

Task. Compute the posterior P(S=t | W =t).

IS ZC444 (BITS Goa) QA slides November 23, 2025 4 / 25

Q3: Sprinkler Network — A Conditional from Given Joint
Terms
Solution. Normalize over S ∈ {t, f }:

P(S=t, W =t)
P(S=t | W =t) =
P(S=t, W =t) + P(S=f , W =t)

0.2781
= ≈ 0.4298 .
0.2781 + 0.369

IS ZC444 (BITS Goa) QA slides November 23, 2025 4 / 25

HMM Basics: Identify Components & Assumptions

Consider the umbrella/rain example introduced in class.

Tasks.
1 Name the hidden state variable Xt and the observation variable Et .
2 State the first-order Markov assumption for the transition model and
the sensor Markov assumption for the observation model.
3 Using the CPTs shown on the slide (time-homogeneous):

P(Rt =t | Rt−1 =t) = 0.7, P(Rt =t | Rt−1 =f ) = 0.3,

P(Ut =t | Rt =t) = 0.9, P(Ut =t | Rt =f ) = 0.2,

list the two matrices these correspond to.

IS ZC444 (BITS Goa) QA slides November 23, 2025 5 / 25

HMM Basics: Identify Components & Assumptions

Solution. Answers.
1 Xt ≡ Raint ∈ {t, f } (hidden state), Et ≡ Umbrellat ∈ {t, f }
(observed).
2 Transition (first-order) Markov: P(Xt | X0:t−1 ) = P(Xt | Xt−1 ).
Sensor Markov: P(Et | X0:t , E1:t−1 ) = P(Et | Xt ).
 
0.3 0.7
3 Transition matrix (rows Xt−1 ; cols Xt ): if columns are
0.7 0.3
(f , t).  
0.8 0.2
Emission matrix (rows Xt ; cols Et ): if columns are (f , t).
0.1 0.9

IS ZC444 (BITS Goa) QA slides November 23, 2025 5 / 25

HMM Joint Factorization & Parameter Counting

Let an HMM have N hidden states, M observation symbols, horizon T

(hidden X0 , . . . , XT , observations E1 , . . . , ET ).
Tasks.
1 Write the HMM joint factorization P(X0:T , E1:T ).

IS ZC444 (BITS Goa) QA slides November 23, 2025 6 / 25

HMM Joint Factorization & Parameter Counting

Solution. Solutions.
QT
1 P(X0:T , E1:T ) = P(X0 ) t=1 P(Xt | Xt−1 ) P(Et | Xt ).

IS ZC444 (BITS Goa) QA slides November 23, 2025 6 / 25

Single-Step Likelihoods (No Inference)

Using the umbrella HMM CPTs from class:

P(Rt =t | Rt−1 =t) = 0.7, P(Rt =f | Rt−1 =t) = 0.3,

P(Ut =t | Rt =t) = 0.9, P(Ut =t | Rt =f ) = 0.2.

Tasks. Given Rt−1 =t, compute:
1 P(Rt =t, Ut =t | Rt−1 =t),
2 P(Rt =f , Ut =t | Rt−1 =t),
3 the likelihood ratio of (1) to (2).

IS ZC444 (BITS Goa) QA slides November 23, 2025 7 / 25

Single-Step Likelihoods (No Inference)

Solution. Solutions.
1 P(Rt =t | Rt−1 =t) P(Ut =t | Rt =t) = 0.7 × 0.9 = 0.63 .
2 P(Rt =f | Rt−1 =t) P(Ut =t | Rt =f ) = 0.3 × 0.2 = 0.06 .
3 Ratio = 0.63/0.06 = 10.5 .

IS ZC444 (BITS Goa) QA slides November 23, 2025 7 / 25

Q1: Entropy of a Simple Labeled Set

A tiny dataset S has 8 examples with target labels: Yes=5, No=3.

P
Task. Compute the entropy H(S) = − c p(c) log2 p(c).

IS ZC444 (BITS Goa) QA slides November 23, 2025 8 / 25

Q1: Entropy of a Simple Labeled Set

Solution. p(Yes) = 58 = 0.625, p(No) = 38 = 0.375.

H(S) = − 0.625 log2 0.625 + 0.375 log2 0.375 ≈ 0.954 bits .

IS ZC444 (BITS Goa) QA slides November 23, 2025 8 / 25

Q: Compute Information Gain for a Toy Split

A labeled set S has |S| = 12 examples with class counts: Yes = 7, No = 5.

A candidate attribute A has two values v1 , v2 that partition S as:

Sv1 : Yes = 6, No = 2 (|Sv1 | = 8), Sv2 : Yes = 1, No = 3 (|Sv2 | = 4).

Tasks.
1 Compute the parent entropy H(S).
P |Sv |
2 Compute the weighted child entropy v ∈{v1 ,v2 } |S| H(Sv ).

IG (S, A) = H(S) − v |S|S|v | H(Sv ).

P
3 Compute the information gain

IS ZC444 (BITS Goa) QA slides November 23, 2025 9 / 25

Q: Compute Information Gain for a Toy Split
7 5
Solution. Step 1 (parent). pYes = 12 , pNo = 12 .
7 7 5 5
H(S) = − 12 log2 12 − 12 log2 12 ≈ 0.979 bits.
Step 2 (children). For Sv1 :
pYes = 68 = 0.75 ⇒ H(Sv1 ) = − 0.75 log2 0.75 + 0.25 log2 0.25 ≈ 0.811.

For Sv2 : pYes = 14 = 0.25 ⇒ H(Sv2 ) ≈ 0.811.

8 4
Weighted child entropy = 12 · 0.811 + 12 · 0.811 = 0.811 .
Step 3 (gain). IG (S, A) = 0.979 − 0.811 = 0.168 bits (approx.) .

IS ZC444 (BITS Goa) QA slides November 23, 2025 9 / 25

Q2: Pick the Best Root Split by Information Gain

Use the toy “Restaurant-style” subset (target: WillWait) with attributes

Patrons∈ {Few, Many} and Reservation∈ {Yes, No}.
Label counts (from the table shown in class): |S| = 8, Yes=5, No=3.
Task. Compare IG (S, Patrons) and IG (S, Reservation); which attribute
should be the root?

IS ZC444 (BITS Goa) QA slides November 23, 2025 10 / 25

Q2: Pick the Best Root Split by Information Gain

Solution. From the counts: splitting on Patrons yields pure children, so

IG (S, Patrons) = H(S) ≈ 0.954.
For Reservation, the weighted child entropy is ≈ 0.951, so
IG (S, Reservation) ≈ 0.003.
⇒ Choose Patrons as the root (higher information gain).

IS ZC444 (BITS Goa) QA slides November 23, 2025 10 / 25

Q3: Simple Ways to Reduce Overfitting in Trees

Select all settings that typically help prevent an overfit decision tree (no
code needed):
1 Increase maximum depth to a very large number.

2 Set a minimum number of samples per leaf.

3 Limit the maximum tree depth.

4 Post-prune weak branches using a validation set.

IS ZC444 (BITS Goa) QA slides November 23, 2025 11 / 25

Q3: Simple Ways to Reduce Overfitting in Trees

Solution. Helpful: 2, 3, 4 .
(2) Larger leaves are stabler; (3) shallower trees curb variance; (4) pruning
trims weak subtrees using held-out validation. (1) typically increases
overfitting.

IS ZC444 (BITS Goa) QA slides November 23, 2025 11 / 25

Perceptron: One Update Step

A perceptron predicts ŷ = step(w > x + b) with update

w ← w + η(y − ŷ )x, b ← b + η(y − ŷ ). Given x = (2, −1),
w = (0.5, 0.5), b = 0, learning rate η = 0.1.
If the true label is y = 0, compute the prediction ŷ and the updated
(w , b).

IS ZC444 (BITS Goa) QA slides November 23, 2025 12 / 25

Perceptron: One Update Step

Solution. Compute
w > x + b = 0.5 · 2 + 0.5 · (−1) + 0 = 1 − 0.5 = 0.5 ⇒ ŷ = step(0.5) = 1.
y − ŷ = 0 − 1 = −1.
w ← (0.5, 0.5) + 0.1(−1)(2, −1) = (0.5, 0.5) + (−0.2, 0.1) = (0.3, 0.6).
b ← 0 + 0.1(−1) = −0.1.
⇒ Updated parameters: w = (0.3, 0.6), b = −0.1 .

IS ZC444 (BITS Goa) QA slides November 23, 2025 12 / 25

Activation Functions: Identify the Properties

Match each activation to its typical output range / behavior. Choose all
that apply.
(A) Sigmoid (i) outputs in [0, 1]
(B) Tanh (ii) outputs in [−1, 1]
(C) ReLU (iii) zero for negative inputs, linear for positive
(iv) can saturate and cause vanishing gradients at extremes
Which pairs (function → property) are correct?

IS ZC444 (BITS Goa) QA slides November 23, 2025 13 / 25

Activation Functions: Identify the Properties

Solution. Correct matches:

(A) Sigmoid → (i) and (iv); (B) Tanh → (ii) and (iv); (C) ReLU →
(iii).
Notes: Sigmoid maps to [0, 1] and saturates near 0/1; Tanh maps to
[−1, 1] and also saturates; ReLU is 0 for x < 0, identity for x > 0.

IS ZC444 (BITS Goa) QA slides November 23, 2025 13 / 25

Q-Learning: Single-Step Update

Use the Q-learning update:

Q(s 0 , a0 ) − Q(s, a) .
 
Q(s, a) ← Q(s, a) + α r + γ max
0 a

Given Q(s, a) = 2.0, reward r = 1, γ = 0.9, maxa0 Q(s 0 , a0 ) = 3.5, and

α = 0.2.
Compute the target and the updated Q(s, a).

IS ZC444 (BITS Goa) QA slides November 23, 2025 14 / 25

Q-Learning: Single-Step Update

Solution. Target
= r + γ maxa0 Q(s 0 , a0 ) = 1 + 0.9 × 3.5 = 1 + 3.15 = 4.15.
Update = 2.0 + 0.2 (4.15 − 2.0) = 2.0 + 0.2 × 2.15 = 2.0 + 0.43 = 2.43 .

IS ZC444 (BITS Goa) QA slides November 23, 2025 14 / 25

Q1: 8-Queens — States and Neighbors

In the 8-queens encoding with exactly one queen per column:

Tasks.
1 How many distinct states are possible?
2 If a neighbor is defined by moving one column’s queen to a different
row in the same column, how many neighbors does any state have?

IS ZC444 (BITS Goa) QA slides November 23, 2025 15 / 25

Q1: 8-Queens — States and Neighbors

Solution. Solutions.
1 Each of 8 columns chooses 1 of 8 rows: 88 states.
2 For each of 8 columns, the queen can move to 8 − 1 = 7 other rows:
8 × 7 = 56 neighbors.

IS ZC444 (BITS Goa) QA slides November 23, 2025 15 / 25

Q2: Hill-Climbing Variants — Pick the Correct Statements

Select all correct statements.

1 Steepest-ascent hill climbing evaluates all neighbors and moves to the

best-improving one.
2 Stochastic hill climbing may examine a randomly chosen neighbor

rather than all neighbors.

3 Random-restart hill climbing repeats hill climbing from different

random initial states.

4 Hill climbing never gets stuck on local maxima.

IS ZC444 (BITS Goa) QA slides November 23, 2025 16 / 25

Q2: Hill-Climbing Variants — Pick the Correct Statements

Solution. Correct: 1, 2, 3 .
(4) is false: hill climbing can get stuck on local
maxima/plateaus/shoulders.

IS ZC444 (BITS Goa) QA slides November 23, 2025 16 / 25

ACO: One Step of Probabilistic Choice

From node i, two feasible neighbors j1 , j2 have τij1 = 2, ηij1 = 3 and

τij2 = 1, ηij2 = 1. With α = 1, β = 1, compute the selection probabilities
p(i → j1 ) and p(i → j2 ) using

τijα ηijβ
p(i → j) = P .
α β
k∈Allowed(i) τik ηik

IS ZC444 (BITS Goa) QA slides November 23, 2025 17 / 25

ACO: One Step of Probabilistic Choice

Solution. Scores: j1 : 2 · 3 = 6, j2 : 1 · 1 = 1. Sum = 7.

p(i → j1 ) = 6/7 ≈ 0.857 , p(i → j2 ) = 1/7 ≈ 0.143 .

IS ZC444 (BITS Goa) QA slides November 23, 2025 17 / 25

ACO: Evaporation and Deposit (Concept Check)

In ACO, pheromone on edge (u, v ) is updated by

τuv ← (1 − ρ)τuv + ∆τuv , with 0 < ρ < 1.
Tasks.
1 What does the evaporation term (1 − ρ)τuv achieve?
2 When is ∆τuv typically positive, and why?

IS ZC444 (BITS Goa) QA slides November 23, 2025 18 / 25

ACO: Evaporation and Deposit (Concept Check)

Solution.
1 Evaporation “forgets” old trails, preventing overcommitment and
encouraging exploration.
2 ∆τuv > 0 when (u, v ) appears in good/elite solutions (e.g.,
iteration-best or best-so-far tour), reinforcing components that helped
produce low-cost solutions.

IS ZC444 (BITS Goa) QA slides November 23, 2025 18 / 25

PSO: One Velocity/Position Update

Use the canonical PSO update with w = 0.5, c1 = c2 = 1.

Velocity update formula: v ← w v + c1 r1 (p − x) + c2 r2 (g − x)
Position update formula: x ← x + v
Current particle: x = (2, 0), v = (1, −1); personal best p = (1, 1); global
best g = (0, 0).
Assume r1 = r2 = 0.5. Compute the new v and x.

IS ZC444 (BITS Goa) QA slides November 23, 2025 19 / 25

PSO: One Velocity/Position Update

Solution. v ← 0.5(1, −1) + 1 · 0.5[(1, 1) − (2, 0)] + 1 · 0.5[(0, 0) − (2, 0)]

= (0.5, −0.5) + 0.5(−1, 1) + 0.5(−2, 0) =
(0.5, −0.5) + (−0.5, 0.5) + (−1, 0) = (−1, , 0).
x ← x + v = (2, 0) + (−1, 0) = (1, 0) ; new velocity (−1, 0) .

IS ZC444 (BITS Goa) QA slides November 23, 2025 19 / 25

Alpha–Beta: How Much Can It Save?

A game tree has branching factor b = 4 and search depth m = 6. Tasks.

1 How many leaf nodes does plain minimax (no pruning) examine (big-O
form and numeric)?
2 In the best move-ordering case for alpha–beta, about how many leaves
are examined?
3 Briefly state why move ordering matters for pruning.

IS ZC444 (BITS Goa) QA slides November 23, 2025 20 / 25

Alpha–Beta: How Much Can It Save?

Solution. (1) Minimax examines O(b m ) = 46 = 4096 leaves.

(2) Best-case alpha–beta is about O(b m/2 ) = 43 = 64 leaves.
(3) Seeing stronger moves first tightens α, β bounds early, so more
branches fail the bounds and get cut off.

IS ZC444 (BITS Goa) QA slides November 23, 2025 20 / 25

Alpha–Beta Cutoff on a Tiny Tree

Root is MAX with two MIN children B and C . Leaf utilities (left→right):

B : (3, 12, 8), C : (2, 6, 9).

Nodes are visited left-to-right. Tasks.

1 What value does MIN return at B? What is MAX’s α after finishing
B?
2 While evaluating C , show the first point at which a cutoff occurs
(state the rule).
3 Which leaves of C are not examined?

IS ZC444 (BITS Goa) QA slides November 23, 2025 21 / 25

Alpha–Beta Cutoff on a Tiny Tree

Solution. (1) B = min(3, 12, 8) = 3 ; after B, MAX has α = 3 .

(2) At C (a MIN node), first leaf 2 sets βC = 2. Since βC ≤ α (i.e.,
2 ≤ 3), we trigger a beta cutoff and stop exploring C .
(3) The remaining leaves 6 and 9 under C are pruned.

IS ZC444 (BITS Goa) QA slides November 23, 2025 21 / 25

Chess Tie-In: Simple Evaluation & Move Ordering

Basic material values (centipawns): Pawn=100, Knight/Bishop=300,

Rook=500, Queen=900.
From the current position, consider three plausible moves for MAX:
1 Capture a pawn safely (+100).
2 Develop a minor piece (no immediate material change, ≈ 0).
3 Retreat a bishop to avoid a threat (−30 due to lost activity).
Tasks.
1 Which move should be examined first to encourage alpha–beta
cutoffs?
2 Give a one-line reason connecting this to move ordering heuristics.

IS ZC444 (BITS Goa) QA slides November 23, 2025 22 / 25

Chess Tie-In: Simple Evaluation & Move Ordering

Solution. (1) Examine the capture (+100) first.

(2) High-value/capturing moves likely produce extreme evaluations earlier,
tightening α, β and increasing pruning; this is a standard move-ordering
heuristic used with alpha–beta in chess.

IS ZC444 (BITS Goa) QA slides November 23, 2025 22 / 25

Forward Chaining in FOL: Assumptions & Properties

Consider a first-order knowledge base intended for forward chaining.

Tasks.
1 List the standard assumptions on the KB and query α under which
FOL forward chaining is applied in class.
2 Under these assumptions, state whether forward chaining is sound
and/or complete.
3 Name one practical tweak to make forward chaining more efficient.

IS ZC444 (BITS Goa) QA slides November 23, 2025 23 / 25

Forward Chaining in FOL: Assumptions & Properties

Solution. Solutions.
1 Assumptions: (i) all sentences are definite clauses; (ii) the query α is
an atomic sentence; (iii) only universal quantifiers (no existentials);
(iv) no function symbols.
2 For first-order definite-clause KBs under these restrictions, forward
chaining is sound and complete.
3 Examples: index the KB for fast retrieval; order conjuncts in patterns;
avoid redundant rule matches (incremental FC).

IS ZC444 (BITS Goa) QA slides November 23, 2025 23 / 25

Generalized Modus Ponens + Unification (Easy Step)


Rule: ∀x King (x) ∧ Greedy (x) ⇒ Evil(x) .
Facts: King (John), Greedy (John).
Tasks.
1 Provide a most general unifier θ that matches the rule’s premise with
the facts.
2 Apply generalized Modus Ponens (GMP) to infer a new ground fact.

IS ZC444 (BITS Goa) QA slides November 23, 2025 24 / 25

Generalized Modus Ponens + Unification (Easy Step)

Solution. Solutions.
1 θ = {x/John} unifies King (x) with King (John) and Greedy (x) with
Greedy (John).
2 By GMP, infer Evil(John) .

IS ZC444 (BITS Goa) QA slides November 23, 2025 24 / 25

Forward Chaining: First Inferred Facts in the “West–Nono”
KB
KB excerpts (time-homogeneous):



∀x Missile(x) ⇒ Weapon(x) , ∀x Enemy (x, America)
⇒ Hostile(x) ,
∀x Missile(x) ∧ Owns(Nono, x) ⇒ Sells(West, x, Nono) ,
American(West), Enemy (Nono, America), Missile(M1),
Owns(Nono, M1), and
∀x ∀y ∀z American(x)

∧ Weapon(y ) ∧ Hostile(z) ∧ Sells(x, y , z) ⇒
Criminal(x) .
Tasks. Using one or two forward-chaining steps, list three new atomic
facts you can infer before concluding anything about Criminal(West).
Then state the final conclusion.

IS ZC444 (BITS Goa) QA slides November 23, 2025 25 / 25

Forward Chaining: First Inferred Facts in the “West–Nono”
KB
Solution. Solutions. From the rules and ground facts:

Weapon(M1) , Hostile(Nono) , Sells(West, M1, Nono) .

Now the last rule’s antecedent holds for x=West, y =M1, z=Nono, so
conclude Criminal(West) .

IS ZC444 (BITS Goa) QA slides November 23, 2025 25 / 25