COS3751
EXAM
PACK
2025
,COS3751 October/November 2024 Exam -
Complete Solutions
Question 1: State Spaces [16]
Hungarian Forint and Mexican Peso Puzzle
Initial: F F _ P P
Goal: P P _ F F
(a) State Representation (2 marks)
State representation: S = [pos0, pos1, pos2, pos3, pos4]
Where each position contains:
• 'F' for Forint coin
• 'P' for Peso coin
• '_' (or 'E') for Empty cell
Example: S = ['F', 'F', '_', 'P', 'P']
(b) Start and Goal States (4 marks)
Start State: S₀ = ['F', 'F', '_', 'P', 'P']
Representing two Forint coins on the left, empty cell in middle, two Peso coins on the right.
Goal State: S_goal = ['P', 'P', '_', 'F', 'F']
Representing two Peso coins on the left, empty cell in middle, two Forint coins on the right.
(c) Adequacy of Representation (2 marks)
,This representation adequately defines any state because:
1. Complete information: Every cell's contents are explicitly represented (all 5 positions)
2. Unique identification: Each configuration is uniquely identifiable - no ambiguity
3. Legal move determination: We can determine all valid moves by:
o Finding the empty cell position
o Checking adjacent cells for slide moves
o Checking cells two positions away for hop moves
4. Goal testing: Easy comparison with goal state using simple equality check
5. Fixed size: Always 5 positions, maintaining consistency across all states
6. Sufficient detail: Contains exactly the necessary information - no more, no less
(d) Operators (5 marks)
Four operators with preconditions and effects:
1. Forint_Slide(S, i)
• Precondition: S[i] = 'F' AND S[i+1] = '_' AND i < 4
• Effect: Swap S[i] and S[i+1]
• Example: ['F', 'F', '', 'P', 'P'] → ['F', '', 'F', 'P', 'P'] (Forint at position 1 slides right to
position 2)
2. Forint_Hop(S, i)
• Precondition: S[i] = 'F' AND S[i+1] ∈ {'F', 'P'} AND S[i+2] = '_' AND i ≤ 2
• Effect: S[i] ↔ S[i+2] (Forint jumps right over another coin)
• Example: ['F', 'P', '', 'P', 'F'] → ['', 'P', 'F', 'P', 'F'] (Forint at position 0 hops over Peso at
position 1 to empty position 2)
3. Peso_Slide(S, i)
• Precondition: S[i] = 'P' AND S[i-1] = '_' AND i > 0
• Effect: Swap S[i] and S[i-1]
, • Example: ['F', 'F', '', 'P', 'P'] → ['F', 'F', 'P', '', 'P'] (Peso at position 3 slides left to
position 2)
4. Peso_Hop(S, i)
• Precondition: S[i] = 'P' AND S[i-1] ∈ {'F', 'P'} AND S[i-2] = '_' AND i ≥ 2
• Effect: S[i] ↔ S[i-2] (Peso jumps left over another coin)
• Example: ['', 'F', 'P', 'P', 'F'] → ['P', 'F', '', 'P', 'F'] (Peso at position 2 hops left over
Forint at position 1 to empty position 0)
(e) Number of Possible States (3 marks)
Calculation:
We have:
• 2 Forint coins (indistinguishable from each other)
• 2 Peso coins (indistinguishable from each other)
• 1 Empty cell
• 5 positions total
Formula: Number of distinct arrangements = 5! / (2! × 2! × 1!)
Computation:
• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 2! × 2! × 1! = 2 × 2 × 1 = 4
• Total = = 30 possible states
Question 2: Machine Learning [16]
Engineers and Interns Crossing Problem
Given:
EXAM
PACK
2025
,COS3751 October/November 2024 Exam -
Complete Solutions
Question 1: State Spaces [16]
Hungarian Forint and Mexican Peso Puzzle
Initial: F F _ P P
Goal: P P _ F F
(a) State Representation (2 marks)
State representation: S = [pos0, pos1, pos2, pos3, pos4]
Where each position contains:
• 'F' for Forint coin
• 'P' for Peso coin
• '_' (or 'E') for Empty cell
Example: S = ['F', 'F', '_', 'P', 'P']
(b) Start and Goal States (4 marks)
Start State: S₀ = ['F', 'F', '_', 'P', 'P']
Representing two Forint coins on the left, empty cell in middle, two Peso coins on the right.
Goal State: S_goal = ['P', 'P', '_', 'F', 'F']
Representing two Peso coins on the left, empty cell in middle, two Forint coins on the right.
(c) Adequacy of Representation (2 marks)
,This representation adequately defines any state because:
1. Complete information: Every cell's contents are explicitly represented (all 5 positions)
2. Unique identification: Each configuration is uniquely identifiable - no ambiguity
3. Legal move determination: We can determine all valid moves by:
o Finding the empty cell position
o Checking adjacent cells for slide moves
o Checking cells two positions away for hop moves
4. Goal testing: Easy comparison with goal state using simple equality check
5. Fixed size: Always 5 positions, maintaining consistency across all states
6. Sufficient detail: Contains exactly the necessary information - no more, no less
(d) Operators (5 marks)
Four operators with preconditions and effects:
1. Forint_Slide(S, i)
• Precondition: S[i] = 'F' AND S[i+1] = '_' AND i < 4
• Effect: Swap S[i] and S[i+1]
• Example: ['F', 'F', '', 'P', 'P'] → ['F', '', 'F', 'P', 'P'] (Forint at position 1 slides right to
position 2)
2. Forint_Hop(S, i)
• Precondition: S[i] = 'F' AND S[i+1] ∈ {'F', 'P'} AND S[i+2] = '_' AND i ≤ 2
• Effect: S[i] ↔ S[i+2] (Forint jumps right over another coin)
• Example: ['F', 'P', '', 'P', 'F'] → ['', 'P', 'F', 'P', 'F'] (Forint at position 0 hops over Peso at
position 1 to empty position 2)
3. Peso_Slide(S, i)
• Precondition: S[i] = 'P' AND S[i-1] = '_' AND i > 0
• Effect: Swap S[i] and S[i-1]
, • Example: ['F', 'F', '', 'P', 'P'] → ['F', 'F', 'P', '', 'P'] (Peso at position 3 slides left to
position 2)
4. Peso_Hop(S, i)
• Precondition: S[i] = 'P' AND S[i-1] ∈ {'F', 'P'} AND S[i-2] = '_' AND i ≥ 2
• Effect: S[i] ↔ S[i-2] (Peso jumps left over another coin)
• Example: ['', 'F', 'P', 'P', 'F'] → ['P', 'F', '', 'P', 'F'] (Peso at position 2 hops left over
Forint at position 1 to empty position 0)
(e) Number of Possible States (3 marks)
Calculation:
We have:
• 2 Forint coins (indistinguishable from each other)
• 2 Peso coins (indistinguishable from each other)
• 1 Empty cell
• 5 positions total
Formula: Number of distinct arrangements = 5! / (2! × 2! × 1!)
Computation:
• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 2! × 2! × 1! = 2 × 2 × 1 = 4
• Total = = 30 possible states
Question 2: Machine Learning [16]
Engineers and Interns Crossing Problem
Given:
