CBS3004 Artificial Intelligence

Exam revision pack - Assessments 1 to 7

For each assignment: (1) what to write if it comes as a handwritten question (formulas, technique, the worked numbers from your submission) and (2) a short Python program you can remember, which asks for its inputs and reproduces the output of your original code.

#	Assignment	Technique
1a	Missionaries & Cannibals	State space, valid/invalid states, BFS
1b	Water Jug (5L / 3L, goal 4L)	BFS vs DFS vs A*, comparison table
2	Monkey and Banana	A* with admissible heuristic, OPEN/CLOSED
3	8-Queens	Hill climbing + random restart
4	Travelling Salesman	Simulated annealing
5	Wumpus World	Propositional logic + knowledge-based agent
6	At-risk student agent	Naive Bayes, predicate logic, belief updating
7	Toy preference	Entropy, information gain, decision tree
+	One-page formula sheet	Everything on a single page

How to use the programs

Every program reads its data with input(). The Sample input block under each program is exactly what to type to reproduce the assignment's output.
I ran every program next to your original code (same inputs, same random seed where randomness is used) and diffed the output. They match, apart from the small deliberate changes listed below.
Programs are written to be short enough to rewrite from memory: one idea per function, same names as the theory (h, succ, parent, delta, T, alpha...).

Deliberate differences from your submitted code

Assessment 6: the last 'belief change' line was inverted in your code (it printed increased although belief fell from 0.9231 to 0.75). Fixed: it now prints decreased.
Assessment 4: intermediate tours were printed with a hard-coded closing 'A', giving things like ['C','B','D','E','A','A']. Now the tour closes on its own first city. The route graph places cities on a circle (your old coordinates were invented, they were not derived from the distance matrix).
Assessment 5: Q9 and Q10 are merged into one file (grid, derived facts, then exploration log, route, actions).
Assessment 2: the start state is typed in, so you can also type the unsolvable state to see the 'NO SOLUTION' message.
Assessment 1b: the unused DFS depth-limit was dropped (the visited set already prevents loops); output is identical.

Before you revise: things to fix in your handwritten answers

While checking your work I found a few slips. Fixing them takes two minutes and avoids losing marks, and if the same question appears tomorrow you will know the correct version.

Assessment	What I found	Correct version
3 - 8-Queens, Q7	Your example state S = [1,5,8,6,3,7,2,4] is described as 'suppose h = 4', but that exact state is a solution (h = 0).	Use [1,5,8,6,3,7,2,1] (h = 2). Its best neighbour (move column-8 queen to row 4) gives h = 0. See Assessment 3 section.
3 - Q6	Local minimum written as 'lower h than all neighbours' but the example says neighbours have h >= 2.	Local minimum = no neighbour has strictly lower h while h > 0 (neighbours are >= current).
5 - Wumpus, Q1	The drawn grid has R1 at the top (pit and agent end up in the wrong rows). The question says rows are numbered bottom to top.	R4 on top ... R1 at the bottom (agent bottom-left at R1C1). Your coordinate list is correct.
5 - Q8	'This gives us only one valid path'.	Not true: R1C1->R2C1->R2C2->R3C2 is also safe and equally short. Say 'one safe route is ...'.
6 - Part A(e)	'P(Yes\|R) = 0.2 > P(Yes\|NR) = 0.8' is false as an inequality.	0.2 < 0.8, so assignment = Yes is evidence for NR; low attendance and poor quiz outweigh it.
6 - Python	Last belief-change message is inverted (see cover page).	Fixed in this pack.
6 - PDF	The 'Poor Quiz / Assignment = Yes' page appears twice in your PDF.	Check that your page on logical knowledge vs probabilistic belief is really in the submission.
4 - TSP code	Intermediate tours printed with a fixed closing 'A'; graph coordinates are arbitrary.	Fixed (see cover page).
1 - M&C Part B(II)	Valid-state list shows '(0,1,R) -> goal' and has no (0,0).	Goal is (0,0,R).
1b - Water jug	Heuristic min(\|x-4\|,\|y-4\|) is called admissible, but it overestimates: state (1,0) has h = 3 yet only 2 moves are needed. Also your drawn state-space tree has (0,4), (4,2) and repeated (0,0), which are impossible with a 3L jug.	Say A* is optimal here in practice or use h = 1 for non-goal states (always admissible). Draw the tree from the section below.

Everything else I recomputed (entropies, information gains, Naive Bayes, belief updates, TSP distances, A* g/h/f values, Wumpus percepts) agrees with your numbers.

Assessment 1 - Question 1: Missionaries and Cannibals (state space + BFS)

Exam theory

State: (ML, CL, B) with B in {L, R}. Right bank is implied: MR = 3 - ML, CR = 3 - CL.
Initial (3,3,L). Goal (0,0,R).
Safety rule - check BOTH banks: a bank is safe if it has no missionaries, or missionaries >= cannibals. So valid <=> (ML=0 or ML>=CL) and (MR=0 or MR>=CR).
Operators: boat carries (m,c) with 1 <= m+c <= 2, i.e. (1,0) (2,0) (0,1) (0,2) (1,1). Boat on L: new state (ML-m, CL-c, R). Boat on R: (ML+m, CL+c, L). Discard if any count is negative or > 3.
Invalid states (3M, 3C): (ML,CL) in {(1,0), (1,2), (1,3), (2,0), (2,1), (2,3)} with either boat side = 12 states. Reason: exactly 1 or 2 missionaries are on a bank with strictly more cannibals, so they are eaten. (1,2),(1,3),(2,3) are unsafe on the left; (1,0),(2,0),(2,1) force the right bank (2M/3C, 1M/3C, 1M/2C) to be unsafe.
Valid (ML,CL) pairs: (0,0) (0,1) (0,2) (0,3) (1,1) (2,2) (3,0) (3,1) (3,2) (3,3), each with L or R.
Technique: BFS tree from (3,3,L): expand each state with the 5 moves, put a tick on valid, a cross on invalid, never expand a repeated state. BFS returns the shortest solution = 11 crossings.

Step	0	1	2	3	4	5	6	7	8	9	10	11
State	3,3,L	3,1,R	3,2,L	3,0,R	3,1,L	1,1,R	2,2,L	0,2,R	0,3,L	0,1,R	0,2,L	0,0,R
Move	-	2C →	1C ←	2C →	1C ←	2M →	1M1C ←	2M →	1C ←	2C →	1C ←	2C →

4 missionaries + 4 cannibals, boat 2:
- (a) No, unsolvable.
- (b) With a 2-seat boat you can never move enough people while keeping missionaries >= cannibals on both banks; the search runs out of safe states (only 11 reachable) without reaching (0,0,R).
- (c) Make the boat capacity 3 (solvable in 9 crossings), or go back to 3M/3C.

Python (BFS)

from collections import deque
M = int(input("Missionaries: "))
C = int(input("Cannibals: "))
K = int(input("Boat capacity: "))
def safe(m, c):                      # one bank is safe if m==0 or m>=c
    return m >= 0 and c >= 0 and (m == 0 or m >= c)
def valid(s):                        # both banks must be safe
    return safe(s[0], s[1]) and safe(M - s[0], C - s[1])
def moves(s):                        # every legal state after ONE crossing
    ml, cl, b = s
    d = -1 if b == 'L' else 1        # boat leaves left -> people leave left bank
    out = []
    for m in range(K + 1):
        for c in range(K + 1):
            if 1 <= m + c <= K:
                n = (ml + d * m, cl + d * c, 'R' if b == 'L' else 'L')
                if valid(n):
                    out.append((n, f"{m}M,{c}C {'L->R' if b == 'L' else 'R->L'}"))
    return out
start, goal = (M, C, 'L'), (0, 0, 'R')
parent = {start: (None, None)}       # doubles as the visited set
queue = deque([start])
while queue:                         # BFS
    s = queue.popleft()
    if s == goal:
        break
    for n, act in moves(s):
        if n not in parent:
            parent[n] = (s, act)
            queue.append(n)
print(f"\n=== {M} Missionaries, {C} Cannibals, boat capacity {K} ===")
if goal not in parent:
    print(f"NO SOLUTION EXISTS. ({len(parent)} states explored before exhausting the search)")
else:
    path, node = [], goal            # walk back from goal using parent links
    while node is not None:
        prev, act = parent[node]
        path.append((node, act))
        node = prev
    path.reverse()
    print(f"{'Step':<6}{'State (M_L,C_L,B)':<22}{'Move'}")
    for i, (s, act) in enumerate(path):
        print(f"{i:<6}{str(s):<22}{act if act else 'Initial state'}")
    print(f"\nTotal crossings : {len(path) - 1}")
    print(f"States explored : {len(parent)}")

Sample input and key output

3
3
2     <- missionaries, cannibals, boat capacity (try 4 4 2 -> NO SOLUTION, 4 4 3 -> 9 crossings)

Step  State (M_L,C_L,B)      Move
0     (3, 3, 'L')            Initial state
1     (3, 1, 'R')            0M,2C L->R
2     (3, 2, 'L')            0M,1C R->L
3     (3, 0, 'R')            0M,2C L->R
4     (3, 1, 'L')            0M,1C R->L
5     (1, 1, 'R')            2M,0C L->R
6     (2, 2, 'L')            1M,1C R->L
7     (0, 2, 'R')            2M,0C L->R
8     (0, 3, 'L')            0M,1C R->L
9     (0, 1, 'R')            0M,2C L->R
10    (0, 2, 'L')            0M,1C R->L
11    (0, 0, 'R')            0M,2C L->R

Total crossings : 11
States explored : 15

Assessment 1 - Question 2: Water Jug problem (BFS, DFS, A*)

Exam theory

State (x,y): x = litres in the 5L jug, y = litres in the 3L jug, 0<=x<=5, 0<=y<=3. Start (0,0). Goal x = 4.
Always: generate successors, skip already visited states, keep a parent pointer to rebuild the path.

Operator	Condition	Result
Fill 5L	x < 5	(5, y)
Fill 3L	y < 3	(x, 3)
Empty 5L	x > 0	(0, y)
Empty 3L	y > 0	(x, 0)
Pour 5L → 3L	x > 0 and y < 3	p = min(x, 3-y) → (x-p, y+p)
Pour 3L → 5L	y > 0 and x < 5	p = min(y, 5-x) → (x+p, y-p)

Shortest solution (BFS and A, 6 moves):* (0,0) → (5,0) → (2,3) → (2,0) → (0,2) → (5,2) → (4,3).
DFS (8 moves): (0,0) → (0,3) → (3,0) → (3,3) → (5,1) → (0,1) → (1,0) → (1,3) → (4,0). Valid but not shortest.
State-space tree to draw (BFS levels; a new state appears only the first time it is generated, repeats are crossed out):
- L0: (0,0).
- L1: (5,0) [Fill 5L], (0,3) [Fill 3L].
- L2: (5,3) and (2,3) from (5,0) [Fill 3L, Pour 5→3]; (3,0) from (0,3) [Pour 3→5].
- L3: (2,0) from (2,3) [Empty 3L]; (3,3) from (3,0) [Fill 3L].
- L4: (0,2) from (2,0) [Pour 5→3]; (5,1) from (3,3) [Pour 3→5].
- L5: (5,2) from (0,2) [Fill 5L]; (0,1) from (5,1) [Empty 5L].
- L6: (4,3) from (5,2) [Pour 5→3] = goal.
- (0,0), (5,0), (0,3) etc. regenerated in between are repeats. The goal is found at depth 6, which is why BFS gives 6 moves.

Comparison table (from your run)

	BFS	DFS	A*
Data structure	Queue (FIFO)	Stack (LIFO)	Priority queue on f = g + h
Moves found	6	8	6
States explored	13	9	12
Complete?	Yes	Yes (finite space + visited set; may loop without it)	Yes
Optimal?	Yes (all steps cost 1)	No	Yes if h is admissible
Memory	Highest: whole frontier O(bd)	Lowest: current path O(b·m)	O(bd) worst case, but fewer nodes with a good h
Time here	~0.07 ms	~0.02 ms (fastest but not optimal)	~0.04 ms

A*: f(n) = g(n) + h(n); g = moves so far; h(n) = min(|x-4|, |y-4|) in the code. Priority queue = heapq; ties broken with a counter.
Honest note on the heuristic: this h can overestimate (e.g. (1,0): h = 3 but 2 moves suffice via (1,3) then (4,0)). For a guaranteed admissible heuristic use h = 0 at the goal and 1 elsewhere. On this instance A* still returned the optimal 6 moves.
Timing: time.perf_counter() before and after the search; subtract and multiply by 1000 for ms.

Python (BFS + DFS + A* + comparison)

import time, heapq
from collections import deque
X = int(input("Capacity of jug 1: "))
Y = int(input("Capacity of jug 2: "))
G = int(input("Goal litres: "))
START = (0, 0)
def succ(s):                          # all 6 operations
    x, y = s
    out = []
    if x < X: out.append(((X, y), f"Fill jug-{X}L"))
    if y < Y: out.append(((x, Y), f"Fill jug-{Y}L"))
    if x > 0: out.append(((0, y), f"Empty jug-{X}L"))
    if y > 0: out.append(((x, 0), f"Empty jug-{Y}L"))
    if x > 0 and y < Y:
        p = min(x, Y - y)
        out.append(((x - p, y + p), f"Pour jug-{X}L -> jug-{Y}L"))
    if y > 0 and x < X:
        p = min(y, X - x)
        out.append(((x + p, y - p), f"Pour jug-{Y}L -> jug-{X}L"))
    return out
def goal(s): return s[0] == G or s[1] == G
def h(s): return min(abs(s[0] - G), abs(s[1] - G))   # A* heuristic
def build(parent, s):                 # rebuild path from parent links
    path = []
    while s is not None:
        prev, act = parent[s]
        path.append((s, act))
        s = prev
    return path[::-1]
def bfs():
    t = time.perf_counter()
    q, parent, n = deque([START]), {START: (None, None)}, 0
    while q:
        s = q.popleft(); n += 1
        if goal(s): return build(parent, s), n, time.perf_counter() - t
        for nx, a in succ(s):
            if nx not in parent:
                parent[nx] = (s, a); q.append(nx)
    return None, n, time.perf_counter() - t
def dfs():
    t = time.perf_counter()
    st, parent, n = [START], {START: (None, None)}, 0
    while st:
        s = st.pop(); n += 1
        if goal(s): return build(parent, s), n, time.perf_counter() - t
        for nx, a in succ(s):
            if nx not in parent:
                parent[nx] = (s, a); st.append(nx)
    return None, n, time.perf_counter() - t
def astar():
    t = time.perf_counter()
    pq, parent, best, n, c = [(h(START), 0, 0, START)], {START: (None, None)}, {START: 0}, 0, 0
    while pq:
        f, _, g, s = heapq.heappop(pq); n += 1
        if goal(s): return build(parent, s), n, time.perf_counter() - t
        for nx, a in succ(s):
            if nx not in best or g + 1 < best[nx]:
                best[nx] = g + 1; parent[nx] = (s, a); c += 1
                heapq.heappush(pq, (g + 1 + h(nx), c, g + 1, nx))
    return None, n, time.perf_counter() - t
print(f"WATER JUG PROBLEM (Jug-A capacity={X}L, Jug-B capacity={Y}L, Goal={G}L)")
print(f"Start state: {START}")
results = [("BFS", bfs()), ("DFS", dfs()), ("A*", astar())]
for name, (path, n, t) in results:
    print(f"\n--- {'A* Search' if name == 'A*' else name} ---")
    if path is None:
        print("No solution found.")
        continue
    for i, (s, a) in enumerate(path):
        print(f"Step {i}: {s} (start)" if a is None else f"Step {i}: {s} <- {a}")
    print(f"Moves to reach goal : {len(path) - 1}")
    print(f"States explored     : {n}")
    print(f"Execution time      : {t*1000:.4f} ms")
print("\n\n=========== COMPARISON TABLE ===========")
head = f"{'Algorithm':<10}{'Moves':<8}{'States Explored':<18}{'Time (ms)':<12}"
print(head); print("-" * len(head))
for name, (path, n, t) in results:
    print(f"{name:<10}{str(len(path) - 1 if path else 'NA'):<8}{n:<18}{t*1000:<12.4f}")

Sample input and key output

5
3
4     <- jug-1 capacity, jug-2 capacity, goal litres

=========== COMPARISON TABLE ===========
Algorithm Moves   States Explored   Time (ms)
------------------------------------------------
BFS       6       13                0.0394
DFS       8       9                 0.0193
A*        6       12                0.0361

Assessment 2: Monkey and Banana (A* search)

Exam theory

State S = (M, B1, B2, E, K, G): M, B1, B2 in {Door, Centre, Window}; E (elevation) in {floor, onB2, onB1}; K = stacked? (Yes/No); G = has banana? (Yes/No). Size = 3·3·3·3·2·2 = 324 (syntactic).
Initial S0 = (Door, Window, Door, floor, No, No). Goal test: G = Yes (the reachable goal is (Centre, Centre, Centre, onB1, Yes, Yes)).
Remember the rule: everything that moves the monkey needs E = floor, and once K = Yes the boxes are frozen (cannot be pushed).

Operator	Preconditions	Effect	Cost
Walk(x,y)	E=floor, M=x, x≠y	M := y	1
PushB1(x,y)	E=floor, M=B1=x, K=No, x≠y	M := y, B1 := y	2
PushB2(x,y)	E=floor, M=B2=x, K=No, x≠y	M := y, B2 := y	2
Stack	E=floor, M=B1=B2, K=No	K := Yes	3
ClimbOntoB2	E=floor, K=Yes, M=B2	E := onB2	1
ClimbOntoB1	E=onB2, K=Yes	E := onB1	1
Grasp	E=onB1, K=Yes, M=B1=B2=Centre, G=No	G := Yes	1

Admissible heuristic

h(n) = 2·[B2 ≠ Centre] + 2·[B1 ≠ Centre] + 3·[K = No] + climbs(E) + 1·[G = No], where climbs(floor) = 2, climbs(onB2) = 1, climbs(onB1) = 0, and h(goal) = 0. Each term is a different action that must still happen at least once, so nothing is counted twice and there is no climb-down operator. h(S0) = 2+2+3+2+1 = 10 <= h*(S0) = 11.

Admissible: h(n) <= h*(n) for every state, because each term is a lower bound on a required, separate action. Also checked on all 43 reachable states by computer: true.
Consistent: h(n) <= c(n,a,n') + h(n') for every operator: Walk changes nothing (0 <= 1); a push to Centre lowers h by at most 2 (cost 2); Stack lowers h by 3 (cost 3); each climb lowers h by 1 (cost 1); Grasp lowers h by 1 (cost 1). Consistent implies admissible and means a state is never re-opened.

A* procedure to write

f = g + h. OPEN = priority queue ordered by f; tie-break: smaller f, then smaller h, then the state opened earlier. CLOSED = expanded states.
Pop the best node, add to CLOSED, test the goal when it is expanded, generate successors, skip those already in CLOSED, keep the cheaper g if a state is regenerated.
Write for every expansion: state, g, h, f, successors, OPEN list, CLOSED list.

#	Expanded	State (M,B1,B2,E,K,G)	g	h	f
1	S0	(D, W, D, floor, No, No)	0	10	10
2	S3	(C, W, C, floor, No, No)	2	8	10
3	S5	(D, W, C, floor, No, No)	3	8	11
4	S6	(W, W, C, floor, No, No)	3	8	11
5	S8	(C, C, C, floor, No, No)	5	6	11
6	S13	(C, C, C, floor, Yes, No)	8	3	11
7	S16	(C, C, C, onB2, Yes, No)	9	2	11
8	S17	(C, C, C, onB1, Yes, No)	10	1	11
9	S18	(C, C, C, onB1, Yes, Yes) GOAL	11	0	11

Optimal plan (cost 11): PushB2(Door→Centre) 2, Walk(Centre→Window) 1, PushB1(Window→Centre) 2, Stack 3, ClimbOntoB2 1, ClimbOntoB1 1, Grasp 1 = 11.
Why optimal: h is admissible (consistent), and when S18 is expanded every state still in OPEN has f >= 11, so nothing cheaper exists.
Invalid actions (precondition violated):
- Grasp in (C,C,C,floor,Yes,No) - monkey is on the floor, needs E=onB1.
- ClimbOntoB1 in (C,C,C,floor,No,No) - boxes not stacked.
- Stack in (C,W,C,floor,No,No) - B1 is at Window, needs M=B1=B2.
- PushB2 in (W,W,C,floor,No,No) - monkey at Window but B2 at Centre.

Python (A*)

import heapq, itertools
LOC = ['Door', 'Centre', 'Window']
BANANA = 'Centre'                      # banana hangs above the centre
# state = (monkey, B1, B2, elevation, stacked, has_banana)
m  = input("Monkey location (Door/Centre/Window): ")
b1 = input("Box B1 location: ")
b2 = input("Box B2 location: ")
e  = input("Elevation (floor/onB2/onB1): ")
st = input("Stacked? (yes/no): ") == 'yes'
hb = input("Has banana? (yes/no): ") == 'yes'
START = (m, b1, b2, e, st, hb)
def succ(s):                           # (action, cost, new_state)
    m, b1, b2, e, st, hb = s
    out = []
    if e == 'floor':
        for d in LOC:
            if d != m:
                out.append((f'Walk({m} -> {d})', 1, (d, b1, b2, e, st, hb)))
        if b1 == m and not st:
            for d in LOC:
                if d != m:
                    out.append((f'PushB1({m} -> {d})', 2, (d, d, b2, e, st, hb)))
        if b2 == m and not st:
            for d in LOC:
                if d != m:
                    out.append((f'PushB2({m} -> {d})', 2, (d, b1, d, e, st, hb)))
        if m == b1 == b2 and not st:
            out.append(('Stack(B1 on B2)', 3, (m, b1, b2, e, True, hb)))
        if st and m == b2:
            out.append(('ClimbOntoB2', 1, (m, b1, b2, 'onB2', st, hb)))
    elif e == 'onB2' and st:
        out.append(('ClimbOntoB1', 1, (m, b1, b2, 'onB1', st, hb)))
    elif e == 'onB1' and st and not hb and m == b1 == b2 == BANANA:
        out.append(('Grasp(Banana)', 1, (m, b1, b2, e, st, True)))
    return out
def h(s):                              # admissible + consistent heuristic
    m, b1, b2, e, st, hb = s
    if hb: return 0
    return (2 * (b2 != BANANA) + 2 * (b1 != BANANA) + 3 * (not st)
            + {'floor': 2, 'onB2': 1, 'onB1': 0}[e] + 1)
short = {'Door': 'D', 'Centre': 'C', 'Window': 'W'}
def fmt(s):
    m, b1, b2, e, st, hb = s
    return (f"({short[m]}, {short[b1]}, {short[b2]}, {e}, "
            f"{'Yes' if st else 'No'}, {'Yes' if hb else 'No'})")
label = {START: 'S0'}
def name(s):
    if s not in label: label[s] = 'S%d' % len(label)
    return label[s]
def show(pq, closed):                  # print OPEN and CLOSED lists
    best = {}
    for f, hn, c, s, g, _ in pq:
        if s not in best or g < best[s][0]: best[s] = (g, hn, f, c)
    order = sorted(best.items(), key=lambda kv: (kv[1][2], kv[1][1], kv[1][3]))
    print("  OPEN   : " + (", ".join(f"{label[s]}(g={g},h={hn},f={f})"
                                    for s, (g, hn, f, _) in order) or "(empty)"))
    print("  CLOSED : " + ", ".join(label[s] for s in closed))
def is_goal(s): return s[5] is True    # goal test: monkey has the banana
def astar(start):
    cnt = itertools.count()
    pq = [(h(start), h(start), next(cnt), start, 0, [])]   # (f, h, tie, state, g, path)
    best_g, closed, order = {start: 0}, [], []
    while pq:
        f, hn, _, s, g, path = heapq.heappop(pq)
        if s in closed: continue
        closed.append(s)
        order.append((len(closed), name(s), s, g, hn, f))
        print(f"\nIteration {len(closed)}: EXPAND {name(s)} = {fmt(s)}  g={g} h={hn} f={f}")
        if is_goal(s):
            print("  >>> GOAL STATE reached - search stops here.")
            show(pq, closed)
            return path, g, order
        for act, cost, ch in succ(s):
            if ch in closed: continue
            ng = g + cost
            if ch not in best_g or ng < best_g[ch]:
                best_g[ch] = ng
                heapq.heappush(pq, (ng + h(ch), h(ch), next(cnt), ch, ng, path + [(act, cost, ch)]))
                print(f"  generate {name(ch):>4} = {fmt(ch)}  g={ng} h={h(ch)} f={ng + h(ch)}")
        show(pq, closed)
    return None, None, order
print("=" * 78)
print(f"Initial state : {fmt(START)}   h = {h(START)}")
print("Goal test     : has_banana == True")
path, total, order = astar(START)
if path is None:
    print("\n*** NO SOLUTION EXISTS - the OPEN list became empty before a goal state was reached. ***")
else:
    print("\n" + "-" * 78 + "\nSTATE-EXPANSION ORDER\n" + "-" * 78)
    print(f"{'#':>3} {'State':<5} {'(M, B1, B2, elev, stacked, banana)':<42}{'g':>4}{'h':>4}{'f':>4}")
    for i, nm, s, g, hn, f in order:
        print(f"{i:>3} {nm:<5} {fmt(s):<42}{g:>4}{hn:>4}{f:>4}")
    print("\n" + "-" * 78 + "\nOPTIMAL SEQUENCE OF ACTIONS\n" + "-" * 78)
    run = 0
    for i, (act, cost, s) in enumerate(path, 1):
        run += cost
        print(f"{i:>3}. {act:<24} cost = {cost}  cumulative = {run:<3} -> {fmt(s)}")
    print("-" * 78)
    print(f"NUMBER OF ACTIONS : {len(path)}")
    print(f"TOTAL PATH COST   : {total}")
    print("-" * 78)

Sample input

Door
Window
Door
floor
no
no       <- monkey, B1, B2, elevation, stacked?, has banana?

(For the 'no solution' demo type: Centre Window Centre onB2 no no, one per line.)

Key output

  1 S0    (D, W, D, floor, No, No)    0  10  10
  2 S3    (C, W, C, floor, No, No)    2   8  10
  3 S5    (D, W, C, floor, No, No)    3   8  11
  4 S6    (W, W, C, floor, No, No)    3   8  11
  5 S8    (C, C, C, floor, No, No)    5   6  11
  6 S13   (C, C, C, floor, Yes, No)   8   3  11
  7 S16   (C, C, C, onB2, Yes, No)    9   2  11
  8 S17   (C, C, C, onB1, Yes, No)   10   1  11
  9 S18   (C, C, C, onB1, Yes, Yes)  11   0  11
------------------------------------------------------------------------------
OPTIMAL SEQUENCE OF ACTIONS
------------------------------------------------------------------------------
  1. PushB2(Door -> Centre)   cost = 2  cumulative = 2   -> (C, W, C, floor, No, No)
  2. Walk(Centre -> Window)   cost = 1  cumulative = 3   -> (W, W, C, floor, No, No)
  3. PushB1(Window -> Centre) cost = 2  cumulative = 5   -> (C, C, C, floor, No, No)
  4. Stack(B1 on B2)          cost = 3  cumulative = 8   -> (C, C, C, floor, Yes, No)
  5. ClimbOntoB2              cost = 1  cumulative = 9   -> (C, C, C, onB2, Yes, No)
  6. ClimbOntoB1              cost = 1  cumulative = 10  -> (C, C, C, onB1, Yes, No)
  7. Grasp(Banana)            cost = 1  cumulative = 11  -> (C, C, C, onB1, Yes, Yes)
------------------------------------------------------------------------------
NUMBER OF ACTIONS : 7
TOTAL PATH COST   : 11
------------------------------------------------------------------------------

Assessment 3: 8-Queens (hill climbing with random restart)

Exam theory

State: 8-element list, index = column, value = row (one queen per column). Example [1,5,8,6,3,7,2,4]: queen 1 in R1C1, queen 2 in R5C2, ... Search space 8^8 = 16,777,216 states. Column conflicts are impossible by construction.
Same row: ri = rj. Same diagonal: |ri - rj| = |ci - cj| (equal row difference and column difference). Example: (2,3) and (5,6): |2-5| = |3-6| = 3, so they attack.
Heuristic h(n) = number of attacking pairs (i < j) = same-row pairs + diagonal pairs. Goal h = 0. Max h = C(8,2) = 28. Lower is better.
Neighbours: move one queen to another row in its own column: 8 columns × 7 rows = 56 neighbours.
Steepest-ascent hill climbing: compute h for all 56 neighbours, move to the one with the lowest h (random choice among ties); repeat; stop at h = 0 or when no neighbour is strictly better.
Local minimum: current h > 0 and no neighbour has strictly lower h (all neighbours >= current). The algorithm cannot move although the solution exists elsewhere. Related traps: plateau (all neighbours equal), shoulder, ridge.
Random restart: when stuck, generate a new random initial state and climb again; repeat until h = 0. It is complete with probability 1. For 8-queens, steepest ascent solves only about 14% of random starts (about 4 steps when it succeeds, 3 when stuck), so you expect about 1/0.14 = 7 attempts, roughly 22 steps in total (Russell & Norvig).

Worked iteration (computed)

Initial S = [1,5,8,6,3,7,2,1] (rows listed for columns 1..8). Attacking pairs: columns 1 and 8 (both row 1) and columns 7 and 8 (rows 2 and 1, |2-1| = |7-8| = 1, same diagonal), so h = 2. Generate the 56 neighbours and compute h for each. The best are:

Move	Resulting state	h
column 8: row 1 → 4	[1,5,8,6,3,7,2,4]	0 (best)
column 8: row 1 → 7	[1,5,8,6,3,7,2,7]	1
column 1: row 1 → 4, or column 7: row 2 → 4, ...	several	2 (no improvement)

Hill climbing selects the neighbour with the lowest h (2 → 0). It becomes the current state; h = 0, so the algorithm stops: 8-queens solved in 1 move. If instead every neighbour had h >= 2 we would be at a local minimum and restart.

Python

import random
n = int(input("Number of queens (8): "))
init = input("Initial state, rows 0..n-1 separated by spaces (blank = random): ").split()
def h(b):                               # number of attacking pairs
    return sum(b[i] == b[j] or abs(b[i] - b[j]) == j - i
               for i in range(n) for j in range(i + 1, n))
def best_neighbor(b):                   # move one queen inside its column
    cur = h(b)
    nbrs = [b[:c] + [r] + b[c + 1:] for c in range(n) for r in range(n) if b[c] != r]
    hs = [h(x) for x in nbrs]
    best = min(hs)
    if best >= cur:                     # no strictly better neighbour -> local minimum
        return b, cur, True
    return random.choice([x for x, v in zip(nbrs, hs) if v == best]), best, False
def show(b):                            # print chessboard
    for r in range(n):
        print("".join("Q " if b[c] == r else ". " for c in range(n)))
    print()
restarts = 0
while True:
    board = [int(x) for x in init] if init and restarts == 0 else [random.randint(0, n - 1) for _ in range(n)]
    cur = h(board)
    print(f"\n--- Attempt {restarts + 1} ---")
    print(f"Initial State: {board}, h(n) = {cur}")
    moves, stuck = 0, False
    while not stuck and cur > 0:
        board, cur, stuck = best_neighbor(board)
        if not stuck:
            moves += 1
            print(f"Move {moves} -> State: {board}, h(n) = {cur}")
    if cur == 0:
        print("\n*** Solution Found! ***")
        print(f"Final State: {board}")
        print(f"Total Moves to Solve (this attempt): {moves}")
        print(f"Total Restarts: {restarts}")
        print("\nFinal Chessboard:")
        show(board)
        break
    print(f"Local minimum reached with h(n) = {cur}. Initiating random restart...")
    restarts += 1

Sample input

8
(blank line)     <- number of queens, optional initial state (blank = random)

Type 8 and 0 4 7 5 2 6 1 3 to see the 0-move solved case. Rows are printed 0-indexed.

Assessment 4: Travelling Salesman by Simulated Annealing

Exam theory

Tour length: D(S) = sum of d(ci, ci+1) over consecutive cities + d(last, first).
Neighbour: swap two cities of the current tour. ΔE = D(S') - D(S).
Acceptance: if ΔE < 0 accept always. Otherwise compute P = e^(-ΔE/T), draw a random r in [0,1) and accept if r < P.
Cooling (geometric): T_new = α·T, so T_k = T0·α^k. With T0=10, α=0.9: 10, 9, 8.1, 7.29, 6.561 ...
Keep a separate 'best' tour: the current tour may get worse after accepting a bad move, the best never does.
Why accept worse moves: a local minimum is a tour where every swap is worse; pure hill climbing stops there. Accepting a worse tour with probability e^(-ΔE/T) lets the search climb out and explore other regions. At high T almost anything is accepted (exploration); as T falls, bad moves become unlikely (it behaves like hill climbing). A larger ΔE or smaller T gives a smaller probability.
Loop count: stops when T < 0.01. T0=10, α=0.9: k = ln(1000)/ln(1/0.9) = 65.6, so 66 iterations (last T = 0.0106).

Your worked numbers (distance matrix A..E)

Step	Tour	Calculation	Result
1	S: A-B-C-D-E-A	10+35+30+11+12	D(S) = 98
2	S' (swap C,E): A-B-E-D-C-A	10+17+11+30+15	D(S') = 83
3	ΔE = 83 - 98 = -15 < 0		accept S'
4	T = 0.9 × 10		T = 9
5	S'' (swap B,D in S'): A-D-E-B-C-A	20+11+17+35+15 = 98; ΔE = 98 - 83	ΔE = +15 (worse)
6	P = e^(-15/9) = e^(-1.667)		P = 0.189 (18.9%)
7	r = 0.10 < 0.189		accept S'' (current = 98)
8	best so far	S' = A-B-E-D-C-A	83

Useful values: e^-0.5 = 0.607, e^-1 = 0.368, e^-1.667 = 0.189, e^-2 = 0.135, e^-3 = 0.050. Brute force over all 12 distinct tours confirms 83 is the true optimum.

Python

import random, math
import matplotlib.pyplot as plt
n = int(input("Number of cities: "))
cities = input("City names (e.g. A B C D E): ").split()
dist = {a: dict(zip(cities, map(int, input(f"Distances from {a}: ").split()))) for a in cities}
tour = input("Initial tour (e.g. A B C D E): ").split()
T = eval(input("Initial temperature T0: "))
alpha = eval(input("Cooling rate alpha: "))
T_MIN = 0.01
def length(t):                          # closed tour length
    return sum(dist[t[i]][t[(i + 1) % len(t)]] for i in range(len(t)))
cur, cur_d = tour[:], length(tour)
best, best_d = cur[:], cur_d
print("Initial Tour:", cur + [cur[0]])
print("Initial Distance:", cur_d)
while T > T_MIN:
    cand = cur[:]
    i, j = random.sample(range(len(cand)), 2)   # swap two random cities
    cand[i], cand[j] = cand[j], cand[i]
    cand_d = length(cand)
    delta = cand_d - cur_d                      # delta E = D(S') - D(S)
    if delta < 0:
        accept = True                           # better -> always accept
    else:
        accept = random.random() < math.exp(-delta / T)   # worse -> accept with P = e^(-dE/T)
    if accept:
        cur, cur_d = cand, cand_d
        if cur_d < best_d:
            best, best_d = cur[:], cur_d
    print("Temperature:", round(T, 4), "Tour:", cur + [cur[0]], "Distance:", cur_d)
    T = alpha * T                               # cooling: T_new = alpha * T
print("Final Best Tour:", best + [best[0]])
print("Minimum Distance:", best_d)
# route graph (cities placed on a circle, only the order matters)
pos = {c: (math.cos(2 * math.pi * k / n), math.sin(2 * math.pi * k / n)) for k, c in enumerate(cities)}
route = best + [best[0]]
plt.plot([pos[c][0] for c in route], [pos[c][1] for c in route], marker='o')
for c in cities:
    plt.annotate(c, (pos[c][0] + 0.03, pos[c][1] + 0.03))
plt.title("Best TSP Route using Simulated Annealing")
plt.grid(True)
plt.show()

Sample input

5
A B C D E
0 10 15 20 12
10 0 35 25 17
15 35 0 30 28
20 25 30 0 11
12 17 28 11 0
A B C D E
10
0.9

(cities, names, one matrix row per city, initial tour, T0, alpha). Output is random from run to run; a good run ends with Minimum Distance: 83. Integer distances only.

Assessment 5: Wumpus World using logic

Exam theory

Coordinates: RrCc, rows numbered bottom to top. Adjacent = edge-sharing only: (r+1,c), (r-1,c), (r,c+1), (r,c-1). Diagonals are NOT adjacent.
Predicates: P(r,c) pit, W(r,c) wumpus, B(r,c) breeze, S(r,c) stench, G(r,c) gold/glitter, Safe(r,c).
Rules (valid cells only):
- B(r,c) <=> P(r+1,c) ∨ P(r-1,c) ∨ P(r,c+1) ∨ P(r,c-1).
- S(r,c) <=> W(r+1,c) ∨ W(r-1,c) ∨ W(r,c+1) ∨ W(r,c-1).
- Safe(r,c) <=> ¬P(r,c) ∧ ¬W(r,c).
Two inference moves you need:
1. No breeze at a visited cell ⇒ no pit in any neighbour (no stench ⇒ no wumpus in any neighbour).
2. Elimination: from a true disjunction A ∨ B ∨ C ∨ D, if A, B, D are false then C is true.

Fact type	Cells
Agent / Wumpus / Gold	R1C1 / R3C3 / R3C2
Pits	R4C1, R2C4, R1C3
Breeze (neighbours of pits)	R1C2, R1C4, R2C3, R3C1, R3C4, R4C2
Stench (neighbours of wumpus)	R2C3, R3C2, R3C4, R4C3

Facts in logic: P(4,1) P(2,4) P(1,3) W(3,3) G(3,2) B(1,2) B(1,4) B(2,3) B(3,1) B(3,4) B(4,2) S(2,3) S(3,2) S(3,4) S(4,3) Safe(1,1)

Standard proofs (write these in steps)

Q3 - why R2C3 has a breeze: B(2,3) <=> P(3,3) ∨ P(1,3) ∨ P(2,4) ∨ P(2,2). P(1,3) and P(2,4) are true, so the right side is true, hence B(2,3).
Q4 - stench at R3C2: S(3,2) <=> W(4,2) ∨ W(2,2) ∨ W(3,3) ∨ W(3,1). Possible wumpus cells: R4C2, R2C2, R3C3, R3C1.
Q5 - pit at R1C3: B(1,2) <=> P(2,2) ∨ P(1,1) ∨ P(1,3). B(1,2) true; P(1,1) false (start cell) and P(2,2) false (safe) ⇒ P(1,3) true.
Q6 - R2C2 has no percepts: B(2,2) <=> P(3,2) ∨ P(1,2) ∨ P(2,3) ∨ P(2,1) and S(2,2) <=> W(3,2) ∨ W(1,2) ∨ W(2,3) ∨ W(2,1). Every disjunct is false (none of those cells holds a pit or wumpus), so neither percept. R1C3 and R3C3 are diagonal to R2C2 (row difference 1 and column difference 1), not edge-adjacent, so they cannot cause a percept there.
Q7 - wumpus at R3C3: start from the four candidates R4C2, R2C2, R3C3, R3C1. R2C2 is safe ⇒ W(2,2) false. If W were at R4C2 then R4C1 would smell a stench, but it has none ⇒ false. If W were at R3C1 then R2C1 (safe, no stench) and R4C1 would smell it ⇒ false. Only W(3,3) remains ⇒ true.
Q8 - reaching the gold: R1C1 has no breeze/stench ⇒ R2C1 and R1C2 safe. R2C1 has no percepts ⇒ R3C1 and R2C2 safe. R2C2 has no percepts ⇒ R3C2 safe (also R2C3). One safe route: R1C1 → R2C1 → R3C1 → R3C2 (R1C1 → R2C1 → R2C2 → R3C2 is equally good). Actions: MOVE R2C1, MOVE R3C1, MOVE R3C2, GRAB, MOVE R2C2, MOVE R1C2, MOVE R1C1, CLIMB (8 actions).

Python (Q9 grid + Q10 knowledge-based agent)

from collections import deque
N = int(input("Grid size: "))
agent = tuple(map(int, input("Agent (row col): ").split()))
wumpus = tuple(map(int, input("Wumpus (row col): ").split()))
gold = tuple(map(int, input("Gold (row col): ").split()))
pits = [tuple(map(int, p.split(','))) for p in input("Pits (r,c r,c ...): ").split()]
def nb(r, c):                            # 4-directional neighbours inside the grid
    return [(a, b) for a, b in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]
            if 1 <= a <= N and 1 <= b <= N]
breeze = {x for p in pits for x in nb(*p)}   # breeze next to every pit
stench = set(nb(*wumpus))                    # stench next to the wumpus
R = lambda cell: f"R{cell[0]}C{cell[1]}"
def label(cell):
    L = []
    if cell == agent: L.append("AGENT")
    if cell == wumpus: L.append("WUMPUS")
    if cell in pits: L.append("PIT")
    if cell == gold: L.append("GOLD/Glitter")
    if cell in breeze: L.append("Breeze")
    if cell in stench: L.append("Stench")
    return ",".join(L) or "-"
print(f"{N} x {N} WUMPUS WORLD GRID (Row {N} = top ... Row 1 = bottom)")
print("=" * 100)
print(" " * 8 + "".join(f"C{c:<22}" for c in range(1, N + 1)))
for r in range(N, 0, -1):
    print(f" R{r}   " + "".join(f"[{label((r, c)):<21}]" for c in range(1, N + 1)))
print("=" * 100)
print("\nDerived facts:")
print("Pits          :", [R(p) for p in pits])
print("Wumpus        :", R(wumpus))
print("Gold/Glitter  :", R(gold))
print("Breeze cells  :", sorted(R(c) for c in breeze))
print("Stench cells  :", sorted(R(c) for c in stench))
# ---------------- knowledge-based agent ----------------
visited, no_pit, no_wum, safe = set(), set(), set(), {agent}
def visit(cell):
    visited.add(cell)
    b, s = cell in breeze, cell in stench
    if not b: no_pit.update(nb(*cell))       # no breeze -> no pit in neighbours
    if not s: no_wum.update(nb(*cell))       # no stench -> no wumpus in neighbours
    new = [x for x in nb(*cell) if x in no_pit and x in no_wum and x not in safe]
    safe.update(new)                         # Safe = not pit AND not wumpus
    return b, s, new
print("\nSTEP-BY-STEP EXPLORATION LOG\n" + "=" * 70)
frontier, queued = deque([agent]), {agent}
while frontier:                              # BFS but only through proven-safe cells
    cell = frontier.popleft()
    if cell in visited: continue
    b, s, new = visit(cell)
    print(f"Visit {R(cell):<6} | Breeze={b!s:<5} Stench={s!s:<5}", end="")
    print(f" -> newly inferred SAFE: {[R(x) for x in new]}" if new else " -> no new safe cells inferred")
    for x in new:
        if x not in queued:
            frontier.append(x); queued.add(x)
    if cell == gold: break
def route(a, b):                             # shortest path using ONLY safe cells
    q, seen = deque([[a]]), {a}
    while q:
        p = q.popleft()
        if p[-1] == b: return p
        for x in nb(*p[-1]):
            if x in safe and x not in seen:
                seen.add(x); q.append(p + [x])
go, back = route(agent, gold), route(gold, agent)
print("\nFINAL ROUTE (using only logically established Safe cells)\n" + "=" * 70)
print("Route to Gold :", " -> ".join(R(c) for c in go))
print("Route back    :", " -> ".join(R(c) for c in back))
print("\nACTION SEQUENCE\n" + "=" * 70)
for c in go[1:]: print("MOVE ->", R(c))
print("GRAB -> gold picked up at", R(gold))
for c in back[1:]: print("RETURN MOVE ->", R(c))
print("CLIMB -> agent exits the cave from", R(agent))

Sample input

4
1 1
3 3
3 2
4,1 2,4 1,3     <- grid size, agent, wumpus, gold, pits (r,c r,c ...)

Key output

Pits          : ['R4C1', 'R2C4', 'R1C3']
Wumpus        : R3C3
Gold/Glitter  : R3C2
Breeze cells  : ['R1C2', 'R1C4', 'R2C3', 'R3C1', 'R3C4', 'R4C2']
Stench cells  : ['R2C3', 'R3C2', 'R3C4', 'R4C3']

STEP-BY-STEP EXPLORATION LOG
======================================================================
Visit R1C1 | Breeze=False Stench=False -> newly inferred SAFE: ['R2C1', 'R1C2']
Visit R2C1 | Breeze=False Stench=False -> newly inferred SAFE: ['R3C1', 'R2C2']
Visit R1C2 | Breeze=True  Stench=False -> no new safe cells inferred
Visit R3C1 | Breeze=True  Stench=False -> no new safe cells inferred
Visit R2C2 | Breeze=False Stench=False -> newly inferred SAFE: ['R3C2', 'R2C3']
Visit R3C2 | Breeze=False Stench=True  -> no new safe cells inferred

FINAL ROUTE (using only logically established Safe cells)
======================================================================
Route to Gold : R1C1 -> R2C1 -> R3C1 -> R3C2
Route back    : R3C2 -> R2C2 -> R1C2 -> R1C1

ACTION SEQUENCE
======================================================================
MOVE -> R2C1
MOVE -> R3C1
MOVE -> R3C2
GRAB -> gold picked up at R3C2
RETURN MOVE -> R2C2
RETURN MOVE -> R1C2
RETURN MOVE -> R1C1
CLIMB -> agent exits the cave from R1C1

Assessment 6: At-risk student agent (Naive Bayes, logic, belief updating)

Part A - Naive Bayes (theory)

Bayes: P(C | x) = P(x | C)·P(C) / P(x). Naive assumption: attributes are conditionally independent given the class, so P(x1,x2,x3 | C) = Π P(xi | C).
Steps:
- (a) priors P(C) = count(C)/N.
- (b) P(value | C) = count(value and C)/count(C).
- (c) Score(C) = P(C)·ΠP(xi | C).
- (d) Posterior = Score(C) / (sum of scores).
- (e) Predict the class with the larger posterior.
If any count is 0, apply Laplace smoothing: (count + 1) / (count(C) + number of values). Not needed here.

	R (5 students: S3,S4,S7,S8,S10)	NR (5 students: S1,S2,S5,S6,S9)
Prior	P(R) = 5/10 = 0.5	P(NR) = 5/10 = 0.5
Attendance = Low	3/5 = 0.6 (S3,S7,S10)	1/5 = 0.2 (S6)
Quiz = Poor	4/5 = 0.8 (S3,S4,S7,S8)	1/5 = 0.2 (S5)
Assignment = Yes	1/5 = 0.2 (S4)	4/5 = 0.8 (S1,S2,S5,S6)
Score	0.5×0.6×0.8×0.2 = 0.048	0.5×0.2×0.2×0.8 = 0.016
Posterior	0.048/0.064 = 0.75	0.016/0.064 = 0.25

Prediction: R (At Risk). Justification: low attendance (0.6 vs 0.2) and poor quiz (0.8 vs 0.2) are far more common among R students; assignment = Yes favours NR (0.2 < 0.8) but is outweighed.

Part B - Knowledge representation (theory)

Rules (universally quantified over x; write ∀x if asked):
- LowAttendance(x) → NeedsSupport(x)
- PoorQuiz(x) → NeedsSupport(x)
- LowAttendance(x) ∧ PoorQuiz(x) → AtRisk(x)
- AtRisk(x) → NeedsSupport(x)
- AtRisk(x) → RecommendRemedial(x)
- NeedsSupport(x) → Monitor(x)
Facts: LowAttendance(NewStudent), PoorQuiz(NewStudent), AssignmentSubmitted(NewStudent).
Inference by Modus Ponens: NeedsSupport(NewStudent) (from rule 1 or 2); Monitor(NewStudent); AtRisk(NewStudent) (rule 3); RecommendRemedial(NewStudent). Assignment submitted triggers no rule, so logic derives nothing from it.

Part C - Belief updating (theory)

Update: Bk(R) = P(ek | R)·Bk-1(R) / [P(ek | R)·Bk-1(R) + P(ek | NR)·Bk-1(NR)]. B0 = prior = 0.5 / 0.5.
Shortcut (odds form): posterior odds = prior odds × likelihood ratio, LR = P(e | R)/P(e | NR). Belief in R rises if LR > 1 and falls if LR < 1.

Stage	Evidence	LR	Odds R:NR	B(R)	Change
B0	none (prior)	-	1	0.5	-
B1	Attendance = Low	0.6/0.2 = 3	3	0.75	increases
B2	Quiz = Poor	0.8/0.2 = 4	12	0.9231	increases
B3	Assignment = Yes	0.2/0.8 = 0.25	3	0.75	decreases

B3 equals the Naive Bayes posterior from Part A (0.75): a good consistency check to write down.

Logical knowledge vs probabilistic belief

Logical knowledge: crisp true/false facts and rules; conclusions are certain once the premises hold (Low attendance AND Poor quiz ⇒ AtRisk). Cannot express uncertainty or degree, and cannot use evidence that no rule mentions (assignment submitted).
Probabilistic belief: a degree of belief in [0,1] learned from data and revised with every piece of evidence by Bayes' rule. It can go down as well as up (92.3% → 75% after the assignment) and gives a ranking, not a guarantee.
In this agent: logic decides what actions follow (monitor, support, remedial); probability estimates how likely the student is at risk (75%).

Python (Part A + Part D)

import pandas as pd
n = int(input("Number of students: "))
print("Enter each row as: Student Attendance Quiz Assignment Class (e.g. S1 High Good Yes NR)")
df = pd.DataFrame([input().split() for _ in range(n)],
                  columns=["Student", "Attendance", "Quiz", "Assignment", "Class"])
print("HISTORICAL DATASET")
print(df)
a, q, s = input("New student - Attendance Quiz Assignment: ").split()
new = {"Attendance": a, "Quiz": q, "Assignment": s}
print("\nNEW STUDENT")
print(new)
# priors and likelihoods P(class), P(value | class)
classes = ["R", "NR"]
prior, like = {}, {}
for c in classes:
    sub = df[df["Class"] == c]
    prior[c] = len(sub) / len(df)
    like[c] = {k: len(sub[sub[k] == v]) / len(sub) for k, v in new.items()}
print("\nPRIOR PROBABILITIES")
for c in classes: print(f"P({c}) =", prior[c])
print("\nCONDITIONAL PROBABILITIES")
for c in classes:
    print(f"\nFor {c}:")
    for k, v in new.items(): print(f"P({v} | {c}) =", like[c][k])
# naive Bayes scores = prior x product of likelihoods, then normalise
score = {}
for c in classes:
    score[c] = prior[c]
    for p in like[c].values(): score[c] *= p
print("\nNAIVE BAYES SCORES")
for c in classes: print(f"Score({c}) =", score[c])
total = sum(score.values())
post = {c: score[c] / total for c in classes}
ev = ", ".join(new.values())
print("\nPOSTERIOR PROBABILITIES")
for c in classes: print(f"P({c} | {ev}) =", post[c])
pred = max(post, key=post.get)
print("\nFINAL PREDICTION")
print("Predicted Class =", pred)
print("Student is predicted to be AT RISK." if pred == "R" else "Student is predicted to be NOT AT RISK.")
# sequential belief updating B0 -> B1 -> B2 -> B3
def update(r, nr, lr, lnr):
    r, nr = r * lr, nr * lnr
    return r / (r + nr), nr / (r + nr)
names = [f"{a} Attendance", f"{q} Quiz", f"Assignment {s}"]
B = [(prior["R"], prior["NR"])]
for k in new:
    B.append(update(*B[-1], like["R"][k], like["NR"][k]))
table = pd.DataFrame({
    "Stage": ["B0", "B1", "B2", "B3"],
    "Evidence": ["None", names[0], names[0] + " + " + names[1], " + ".join(names)],
    "P(R)": [b[0] for b in B], "P(NR)": [b[1] for b in B]})
print("\nSEQUENTIAL BELIEF UPDATING")
print(table.to_string(index=False))
print("\nBELIEF CHANGE")
for i, nm in enumerate([f"{a} Attendance", f"{q} Quiz", f"Assignment = {s}"], 1):
    print(f"After {nm}: Belief in R", "increased." if B[i][0] > B[i - 1][0] else "decreased.")

Sample input

10
S1 High Good Yes NR
S2 High Good Yes NR
S3 Low Poor No R
S4 High Poor Yes R
S5 High Poor Yes NR
S6 Low Good Yes NR
S7 Low Poor No R
S8 High Poor No R
S9 High Good No NR
S10 Low Good No R
Low Poor Yes

Key output

For R:
P(Low | R) = 0.6
P(Poor | R) = 0.8
P(Yes | R) = 0.2

For NR:
P(Low | NR) = 0.2
P(Poor | NR) = 0.2
P(Yes | NR) = 0.8

NAIVE BAYES SCORES
Score(R) = 0.048
Score(NR) = 0.016000000000000004

POSTERIOR PROBABILITIES
P(R | Low, Poor, Yes) = 0.75
P(NR | Low, Poor, Yes) = 0.25000000000000006

FINAL PREDICTION
Predicted Class = R
Student is predicted to be AT RISK.

SEQUENTIAL BELIEF UPDATING
Stage                                      Evidence     P(R)     P(NR)
   B0                                          None 0.500000  0.500000
   B1                                Low Attendance 0.750000  0.250000
   B2                    Low Attendance + Poor Quiz 0.923077  0.076923
   B3 Low Attendance + Poor Quiz + Assignment Yes 0.750000  0.250000

BELIEF CHANGE
After Low Attendance: Belief in R increased.
After Poor Quiz: Belief in R increased.
After Assignment = Yes: Belief in R decreased.

Assessment 7: Decision tree (ID3: entropy and information gain)

Exam theory

Entropy: H(S) = - Σ pi log2 pi. Here 6 Yes, 4 No: H = -0.6 log2 0.6 - 0.4 log2 0.4 = 0.4422 + 0.5288 = 0.971.
Information gain: IG(S,A) = H(S) - Σv (|Sv|/|S|)·H(Sv). Root = attribute with the highest IG. A pure subset (all Yes or all No) has entropy 0 and becomes a leaf.
Entropy cheat values (Yes,No): (1,0)=0, (1,1)=1, (3,1)=0.811, (2,1)=0.918, (5,1)=0.650, (1,3)=0.811, (1,2)=0.918.

Attribute	Subsets (Yes,No) and entropy	Weighted entropy	IG
Age Group	Young (3,1)=0.811; Middle (2,1)=0.918; Senior (1,2)=0.918	0.4×0.811 + 0.3×0.918 + 0.3×0.918 = 0.8755	0.0955
Toy Type	Puzzle (3,1)=0.811; Robot (0,3)=0; Doll (3,0)=0	0.4×0.811 = 0.3245	0.6465
Color	Bright (5,1)=0.650; Dark (1,3)=0.811	0.6×0.650 + 0.4×0.811 = 0.7144	0.2566
Price Range	Low (4,0)=0; Medium (2,1)=0.918; High (0,3)=0	0.3×0.918 = 0.2755	0.6955

Root = Price Range (highest gain, 0.6955): it gives two pure branches (Low = all Yes, High = all No) so it removes the most uncertainty.
Tree:
- Price Range → Low: Yes (C1,C4,C9,C10)
- Price Range → High: No (C2,C5,C8)
- Price Range → Medium (C3,C6,C7: 2 Yes, 1 No) → split on Color (best remaining attribute, subset gain 0.918):
  - Bright: Yes (C3,C7)
  - Dark: No (C6)
sklearn notes: DecisionTreeClassifier(criterion='entropy') uses the same measure, but after label encoding it makes binary threshold splits (e.g. Price <= 0.5), so its tree looks different from the multiway ID3 tree while giving the same predictions. (Price High-vs-rest and Toy Robot-vs-rest tie at IG 0.557, so the root can be either; random_state=42 picked Price.) Training accuracy 1.0 because the tree is grown to purity (can overfit).
Predictions: (Senior, Puzzle, Bright, High) → No (High price). (Middle, Doll, Dark, Medium) → No (Medium + Dark). Both agree with the hand-drawn tree.
Label encoding is alphabetical: Age {Middle 0, Senior 1, Young 2}; Toy {Doll 0, Puzzle 1, Robot 2}; Color {Bright 0, Dark 1}; Price {High 0, Low 1, Medium 2}; Likes {No 0, Yes 1}.

Python

import pandas as pd
from sklearn.tree import DecisionTreeClassifier, export_text, plot_tree
import matplotlib.pyplot as plt
cols = ["Child", "Age Group", "Toy Type", "Color", "Price Range", "Likes Toy"]
n = int(input("Number of rows: "))
print("Enter rows as: Child Age Toy Color Price Likes (e.g. C1 Young Puzzle Bright Low Yes)")
df = pd.DataFrame([input().split() for _ in range(n)], columns=cols)
print("Original Dataset:")
print(df, "\n")
# label-encode every column (alphabetical order -> 0,1,2..)
features, target = cols[1:5], "Likes Toy"
maps, enc = {}, df.copy()
for c in features + [target]:
    maps[c] = {v: i for i, v in enumerate(sorted(df[c].unique()))}
    enc[c] = df[c].map(maps[c])
    print(f"{c} encoding: {maps[c]}")
print("\nEncoded Dataset:")
print(enc.drop(columns="Child"), "\n")
X, y = enc[features], enc[target]
model = DecisionTreeClassifier(criterion="entropy", random_state=42).fit(X, y)
print("Training accuracy:", model.score(X, y))
print("\nTree rules:")
print(export_text(model, feature_names=features))
classes = sorted(maps[target], key=maps[target].get)     # ['No', 'Yes']
plt.figure(figsize=(14, 8))
plot_tree(model, feature_names=features, class_names=classes, filled=True, rounded=True, fontsize=10)
plt.title("Decision Tree Likes Toy (criterion = entropy)")
plt.savefig("decision_tree.png", dpi=150, bbox_inches="tight")
plt.close()
print("Tree image saved as decision_tree.png")
# predict new children
k = int(input("Number of new children: "))
print("Enter each as: Age Toy Color Price (e.g. Senior Puzzle Bright High)")
new = pd.DataFrame([dict(zip(features, input().split())) for _ in range(k)])
pred = model.predict(pd.DataFrame({c: new[c].map(maps[c]) for c in features}))
new["Likes Toy (Predicted)"] = [classes[int(p)] for p in pred]
print("\nPredictions for new children:")
print(new.to_string(index=False))

Sample input

10
C1 Young Puzzle Bright Low Yes
C2 Young Robot Dark High No
C3 Middle Puzzle Bright Medium Yes
C4 Middle Doll Bright Low Yes
C5 Senior Robot Dark High No
C6 Senior Puzzle Dark Medium No
C7 Young Doll Bright Medium Yes
C8 Middle Robot Bright High No
C9 Senior Doll Bright Low Yes
C10 Young Puzzle Dark Low Yes
2
Senior Puzzle Bright High
Middle Doll Dark Medium

One-page formula sheet

Topic	Remember
M&C	State (ML,CL,B); bank safe if M=0 or M>=C (both banks); boat 1..2 people; BFS; 3M3C = 11 crossings; 4M4C cap 2 impossible, cap 3 = 9.
Water jug	Pour p = min(source, space in target). BFS optimal, DFS not, A* optimal if h admissible. 5/3/4: 6 moves (BFS, A*), DFS 8.
A* (monkey)	f = g + h; admissible h <= h*; consistent h(n) <= c + h(n'). Ties: smaller f, then smaller h, then FIFO. Goal test on expansion. Plan cost 11, 9 expansions.
8-Queens	h = attacking pairs; same row ri=rj; diagonal \|ri-rj\|=\|ci-cj\|; 56 neighbours; local minimum = no strictly better neighbour; random restart until h=0.
Simulated annealing	ΔE = D(S') - D(S); accept if ΔE < 0 else if r < e^(-ΔE/T); T_new = αT. Numbers: 98, 83, -15, T = 9, 98, +15, P = 0.189, r = 0.1 accepts. Best 83.
Wumpus	B(r,c) <=> OR of P in 4 edge-neighbours; S(r,c) <=> OR of W; Safe = ¬P ∧ ¬W; no percept ⇒ neighbours safe; elimination of disjuncts. Route R1C1-R2C1-R3C1-R3C2.
Naive Bayes	Score(C) = P(C)ΠP(xi\|C); normalise. R 0.048, NR 0.016, posterior 0.75 / 0.25 ⇒ At Risk.
Belief update	odds × LR: 1 → 3 → 12 → 3, i.e. 0.5 → 0.75 → 0.9231 → 0.75.
Entropy / IG	H = -Σp log2p; IG = H(S) - Σ(\|Sv\|/\|S\|)H(Sv). H(S)=0.971; IG: Age 0.0955, Toy 0.6465, Color 0.2566, Price 0.6955 ⇒ root Price.

aimahasolution

Maneet Gupta

CBS3004 Artificial Intelligence

Exam revision pack - Assessments 1 to 7

How to use the programs

Deliberate differences from your submitted code

Before you revise: things to fix in your handwritten answers

Assessment 1 - Question 1: Missionaries and Cannibals (state space + BFS)

Exam theory

Python (BFS)

Sample input and key output

Assessment 1 - Question 2: Water Jug problem (BFS, DFS, A*)

Exam theory

Comparison table (from your run)

Python (BFS + DFS + A* + comparison)

Sample input and key output

Assessment 2: Monkey and Banana (A* search)

Exam theory

Admissible heuristic

A* procedure to write

Python (A*)

Sample input

Key output

Assessment 3: 8-Queens (hill climbing with random restart)

Exam theory

Worked iteration (computed)

Python

Sample input

Assessment 4: Travelling Salesman by Simulated Annealing

Exam theory

Your worked numbers (distance matrix A..E)

Python

Sample input

Assessment 5: Wumpus World using logic

Exam theory

Standard proofs (write these in steps)

Python (Q9 grid + Q10 knowledge-based agent)

Sample input

Key output

Assessment 6: At-risk student agent (Naive Bayes, logic, belief updating)

Part A - Naive Bayes (theory)

Part B - Knowledge representation (theory)

Part C - Belief updating (theory)

Logical knowledge vs probabilistic belief

Python (Part A + Part D)

Sample input

Key output

Assessment 7: Decision tree (ID3: entropy and information gain)

Exam theory

Python

Sample input

One-page formula sheet