COS3751
EXAM PACK
, lOMoARcPSD|18222662
COS3751
QUESTIONS 3 October/November 2024
Question 1 State Spaces [16]
In the Hungarian Forint and Mexican Peso puzzle, there is a container with five cells. In the initial state
of the case the two leftmost cells are occupied by a Forint coin each, while two Peso coins occupy the
two rightmost cells. The middle cell is empty. This is illustrated in Figure 1 as follows:
Figure 1: Puzzle Set FFPP
The puzzle involves rearranging the coins one at a time to reach the goal state. In the goal state, the Peso
and Forint are interchanged in Figure 2 as follows:
Figure 2: Puzzle Set PPFF
There are only four permissible moves according to the following expressions:
(i) A Peso Slide – a Peso coin slides one position to the left into an empty cell.
(ii) A Peso Hop – a Peso coin jumps left across one cell containing a coin into an empty cell.
(iii) A Forint Slide – a Forint coin slides one position to the right into an empty cell
(iv) A Forint Hop – a Forint coin jumps right across one cell containing a coin into an empty cell
A cell may never contain more than one coin, and all coins must be in the container after every move.
Therefore
(a) Design a state representation for the problem. (2)
(b) Using your representation, define the start state, and the goal state. (4)
(c) Explain why your representation adequately defines any state that could occur in the problem
(2)
(d) Define the operators for this problem. (5)
(e) How many possible states are there for this problem? (3)
, lOMoARcPSD|18222662
COS3751
QUESTIONS 4 October/November 2024
Question 2 Machine Learning [16]
Three (3) engineers (Alex, Brianna, and Chris) are working late at a robotics lab located on one side of
a large, automated warehouse. To exit the building, they need to pass through a secured door on the
other side. However, the only way to reach the door is by using a small, automated cart that runs along
a narrow track across the warehouse. While searching for a solution, they find two interns who have
been using the cart to move small items between sections of the warehouse. The engineers ask the
interns if they can use the cart to reach the exit. The interns agree, but explain that due to the cart’s
size, it can only carry either both interns together or just one engineer at a time. We can assume that
everyone knows how to operate the cart.
(a) Define a state using a mathematical notation (pictures or any form of graphical notation will
not be accepted). Discuss the appropriateness of your choice and provide an example to show
that it will be suitable to be employed during a search.
(5)
(b) Define the start and goal states using your representation.
(4)
(c) Define an appropriate cost function or functions for this problem.
(2)
(d) Provide a formal definition of a valid action function for this problem – you need not provide a
formal definition for the operation of the function. Discuss the operation of the function and
provide an example to illustrate its use. (5)
Question 3 First Order Logic [20]
Consider the first order logic vocabulary given below.
Joe, Martha constants denoting people
house, mansion constants denoting the type of building a person could live in
happy(o) predicate: person o is happy
car(p) predicate: person p owns a car
job(r) predicate: person r has a job
gym(q) predicate: person q is a gym member
live(s, t) person t lives in a building of type s
Consider the following English statements.
• Joe has a car and a job.
• All the people who are happy are gym members.
• All the people who own cars and have jobs are happy.
• People who live in mansions are happy.
• Anyone who has somewhere to live is happy
(a) Using the vocabulary specified above, express the English statements above in First- order
Logic (FOL). (10)
(b) Convert the FOL statements in bullet points 1 to 3 above to clausal form (CNF). Then use these
CNF statements and resolution refutation to prove that Joe is a member of a gym.
(10)
, lOMoARcPSD|18222662
COS3751
QUESTIONS 5 October/November 2024
Question 4 Searching [18]
Consider the above state graph, with path costs as indicated. Node A is the start node and node J the goal
node in this state graph.
(a) Perform a bi-directional search using the breadth-first search algorithm to find the lowest cost path
between the start node A and the goal node J. Show the expression of the expansion of nodes after each
step. Use the lowest path cost to choose the first node to expand at each search step. Show every
expansion of each of the two breadth-first searches.
(12)
(b) What is the cost of the lowest cost path (as found by your search)?
(2)
(c) Iterative deepening search combines the benefits of depth-first and breadth-first search. When is
iterative deepening the preferred uninformed search method?
(4)
EXAM PACK
, lOMoARcPSD|18222662
COS3751
QUESTIONS 3 October/November 2024
Question 1 State Spaces [16]
In the Hungarian Forint and Mexican Peso puzzle, there is a container with five cells. In the initial state
of the case the two leftmost cells are occupied by a Forint coin each, while two Peso coins occupy the
two rightmost cells. The middle cell is empty. This is illustrated in Figure 1 as follows:
Figure 1: Puzzle Set FFPP
The puzzle involves rearranging the coins one at a time to reach the goal state. In the goal state, the Peso
and Forint are interchanged in Figure 2 as follows:
Figure 2: Puzzle Set PPFF
There are only four permissible moves according to the following expressions:
(i) A Peso Slide – a Peso coin slides one position to the left into an empty cell.
(ii) A Peso Hop – a Peso coin jumps left across one cell containing a coin into an empty cell.
(iii) A Forint Slide – a Forint coin slides one position to the right into an empty cell
(iv) A Forint Hop – a Forint coin jumps right across one cell containing a coin into an empty cell
A cell may never contain more than one coin, and all coins must be in the container after every move.
Therefore
(a) Design a state representation for the problem. (2)
(b) Using your representation, define the start state, and the goal state. (4)
(c) Explain why your representation adequately defines any state that could occur in the problem
(2)
(d) Define the operators for this problem. (5)
(e) How many possible states are there for this problem? (3)
, lOMoARcPSD|18222662
COS3751
QUESTIONS 4 October/November 2024
Question 2 Machine Learning [16]
Three (3) engineers (Alex, Brianna, and Chris) are working late at a robotics lab located on one side of
a large, automated warehouse. To exit the building, they need to pass through a secured door on the
other side. However, the only way to reach the door is by using a small, automated cart that runs along
a narrow track across the warehouse. While searching for a solution, they find two interns who have
been using the cart to move small items between sections of the warehouse. The engineers ask the
interns if they can use the cart to reach the exit. The interns agree, but explain that due to the cart’s
size, it can only carry either both interns together or just one engineer at a time. We can assume that
everyone knows how to operate the cart.
(a) Define a state using a mathematical notation (pictures or any form of graphical notation will
not be accepted). Discuss the appropriateness of your choice and provide an example to show
that it will be suitable to be employed during a search.
(5)
(b) Define the start and goal states using your representation.
(4)
(c) Define an appropriate cost function or functions for this problem.
(2)
(d) Provide a formal definition of a valid action function for this problem – you need not provide a
formal definition for the operation of the function. Discuss the operation of the function and
provide an example to illustrate its use. (5)
Question 3 First Order Logic [20]
Consider the first order logic vocabulary given below.
Joe, Martha constants denoting people
house, mansion constants denoting the type of building a person could live in
happy(o) predicate: person o is happy
car(p) predicate: person p owns a car
job(r) predicate: person r has a job
gym(q) predicate: person q is a gym member
live(s, t) person t lives in a building of type s
Consider the following English statements.
• Joe has a car and a job.
• All the people who are happy are gym members.
• All the people who own cars and have jobs are happy.
• People who live in mansions are happy.
• Anyone who has somewhere to live is happy
(a) Using the vocabulary specified above, express the English statements above in First- order
Logic (FOL). (10)
(b) Convert the FOL statements in bullet points 1 to 3 above to clausal form (CNF). Then use these
CNF statements and resolution refutation to prove that Joe is a member of a gym.
(10)
, lOMoARcPSD|18222662
COS3751
QUESTIONS 5 October/November 2024
Question 4 Searching [18]
Consider the above state graph, with path costs as indicated. Node A is the start node and node J the goal
node in this state graph.
(a) Perform a bi-directional search using the breadth-first search algorithm to find the lowest cost path
between the start node A and the goal node J. Show the expression of the expansion of nodes after each
step. Use the lowest path cost to choose the first node to expand at each search step. Show every
expansion of each of the two breadth-first searches.
(12)
(b) What is the cost of the lowest cost path (as found by your search)?
(2)
(c) Iterative deepening search combines the benefits of depth-first and breadth-first search. When is
iterative deepening the preferred uninformed search method?
(4)
