COS3751
EXAM PACK
,UNIVERSITY EXAMINATIONS
June/July 2021
COS3751
Techniques of Artificial Intelligence
100 Marks
Duration 2 Hours
EXAMINERS:
FIRST: Prof I Sanders
SECOND: Prof E van der Poel
EXTERNAL: Prof P Machanick (Rhodes University)
This paper consists of 8 pages.
Instructions
1. You are expected to provide your own answers to the questions. Getting an-
swers from the Internet (or other sources) could result in disciplinary action.
2. You may type your answers in a word processor (and then print to PDF for
submission) or handwrite your answers (and then scan to PDF).
3. Answer all questions.
4. The mark for each question is given in brackets next to each question.
5. Read each question carefully before answering: always make sure you pro-
vide an answer to what is being asked.
6. Follow the instructions as sent to you by the university to submit your an-
swers.
7. Make sure you leave yourself enough time to upload your answers before
the end of the allowed time.
Remember to complete the Honesty Declaration when submitting your an-
swers. By submitting your answers you are confirming that this is your
own, unaided work.
[TURN PAGE]
, COS3751
2 May/June 2021
Question 1 State Spaces [18]
Block layout This question involves a problem-solving agent. The agent is being asked
to solve the problem of laying out seven identical blocks into a “C” shape where there are
three blocks on the left and two blocks in each of the top and bottom arms – as shown in
Figure 1.
Figure 1: The desired result of block layout as seen from above
(a) Explain why we call this agent a problem-solving agent. (1)
(b) Define a non-graphical (i.e. no pictures) state representation for the problem. Your
state representation should be such that a search algorithm will be able to start the
search at any given state. (2)
(c) Defend your choice by showing that the level of abstraction is sufficient.
(Hint: Your state representation should only encode the necessary information). (2)
(d) What is the initial state? (1)
(e) What is the goal state? (1)
(f) Define the appropriate actions for this problem.
Note that the agent should start by placing a block into the bottom left postion.
Then using the successor function
Result(a, S) 7→ S 0 ,
show how applying each action a to some state S results in some state S 0 . (4)
(g) Using the state representation you defined above, draw the state space for the block
layout problem. (7)
[TURN PAGE]
, COS3751
3 May/June 2021
Question 2 Searching [12]
(a) Consider the following graph:
S(10)
2
8 e(4)
3
5
d(5) 4
k(2)
c(4)
8 3
7
6
j(4) 5 m(1)
5 i(4)
h(9) 4 3 l(1) 1
3
G
Each node shows the ĥ value (estimate to the goal) in parentheses after the node
name. Each edge shows the ĝ value next to it.
Assume that an A∗ search is employed, that the start node is S, and the goal is G.
The first 2 steps (start node added to frontier, the expansion of that node, and the state
of the frontier) are shown in the table below. The node expanded column shows the
ĝ, ĥ, and fˆ values in parentheses after the node name, and the frontier shows the fˆ
value in parentheses after the front-most node in the path has been explored):
Step Node expanded Frontier
1 [< S(10) >]
2 S(0, 10, 10) [< e(6), S >, < d(8), S >, < c(12), S >]
3
4
5
6
7
Complete the table by showing the list of nodes in the order in which they are expanded
(not just explored) and the state of the open queue when the nodes are expanded.
(10)
(b) Explain briefly the difference between Uniform Cost Search and A∗ search. (2)
[TURN PAGE]
EXAM PACK
,UNIVERSITY EXAMINATIONS
June/July 2021
COS3751
Techniques of Artificial Intelligence
100 Marks
Duration 2 Hours
EXAMINERS:
FIRST: Prof I Sanders
SECOND: Prof E van der Poel
EXTERNAL: Prof P Machanick (Rhodes University)
This paper consists of 8 pages.
Instructions
1. You are expected to provide your own answers to the questions. Getting an-
swers from the Internet (or other sources) could result in disciplinary action.
2. You may type your answers in a word processor (and then print to PDF for
submission) or handwrite your answers (and then scan to PDF).
3. Answer all questions.
4. The mark for each question is given in brackets next to each question.
5. Read each question carefully before answering: always make sure you pro-
vide an answer to what is being asked.
6. Follow the instructions as sent to you by the university to submit your an-
swers.
7. Make sure you leave yourself enough time to upload your answers before
the end of the allowed time.
Remember to complete the Honesty Declaration when submitting your an-
swers. By submitting your answers you are confirming that this is your
own, unaided work.
[TURN PAGE]
, COS3751
2 May/June 2021
Question 1 State Spaces [18]
Block layout This question involves a problem-solving agent. The agent is being asked
to solve the problem of laying out seven identical blocks into a “C” shape where there are
three blocks on the left and two blocks in each of the top and bottom arms – as shown in
Figure 1.
Figure 1: The desired result of block layout as seen from above
(a) Explain why we call this agent a problem-solving agent. (1)
(b) Define a non-graphical (i.e. no pictures) state representation for the problem. Your
state representation should be such that a search algorithm will be able to start the
search at any given state. (2)
(c) Defend your choice by showing that the level of abstraction is sufficient.
(Hint: Your state representation should only encode the necessary information). (2)
(d) What is the initial state? (1)
(e) What is the goal state? (1)
(f) Define the appropriate actions for this problem.
Note that the agent should start by placing a block into the bottom left postion.
Then using the successor function
Result(a, S) 7→ S 0 ,
show how applying each action a to some state S results in some state S 0 . (4)
(g) Using the state representation you defined above, draw the state space for the block
layout problem. (7)
[TURN PAGE]
, COS3751
3 May/June 2021
Question 2 Searching [12]
(a) Consider the following graph:
S(10)
2
8 e(4)
3
5
d(5) 4
k(2)
c(4)
8 3
7
6
j(4) 5 m(1)
5 i(4)
h(9) 4 3 l(1) 1
3
G
Each node shows the ĥ value (estimate to the goal) in parentheses after the node
name. Each edge shows the ĝ value next to it.
Assume that an A∗ search is employed, that the start node is S, and the goal is G.
The first 2 steps (start node added to frontier, the expansion of that node, and the state
of the frontier) are shown in the table below. The node expanded column shows the
ĝ, ĥ, and fˆ values in parentheses after the node name, and the frontier shows the fˆ
value in parentheses after the front-most node in the path has been explored):
Step Node expanded Frontier
1 [< S(10) >]
2 S(0, 10, 10) [< e(6), S >, < d(8), S >, < c(12), S >]
3
4
5
6
7
Complete the table by showing the list of nodes in the order in which they are expanded
(not just explored) and the state of the open queue when the nodes are expanded.
(10)
(b) Explain briefly the difference between Uniform Cost Search and A∗ search. (2)
[TURN PAGE]
