Question 1 [ 2 + 4 + 2 + 2 + 4 = 14 marks ]
(a) Write LISP code for a function average, which takes exactly two numbers as input parameters, and returns the average of these numbers.
(b) LISP functions are ‘first-class objects’. What are the four properties possessed by first class objects?
(c) What would be returned by the following?
> (mapcar #'(lambda (x) (- x 1)) ‘(0 2 4 6))
(d) Consider the following LISP function that takes one argument, a-list:
(defun function-A (a-list)
(cond ((null a-list) 0)
(t (+ (car a-list) (function-A (cdr a-list))))))
What would the function’s output be if it was run as follows:
> (function-A ‘(3 2 1 0))
Page – 2
(e) Write a LISP function largest that takes a list of numbers as its argument, and returns the largest element of the list.
Page – 3
Question 2 [ 2 + 2 + 2 + 2 = 8 marks ]
Below is a tree structure that contains 20 nodes. Node A is the start node. Nodes J and O are goal nodes.
A
BCDE
FGH IJKLMN
O PQRS
T
Write down the nodes which are visited in sequential order when conducting each of the following searches. Stop the search when either of the two goals is found.
(a) depth-first search
(b) breadth-first search
(c) depth-first search with depth limit of two
(d) depth-first search with iterative deepening
Page – 4
Question 3 [ (1 + 1 + 1 + 1) + 2 + 4 = 10 marks ]
(a) Answer each of the following:
(i) What is the time complexity of a search usually measured in terms of?
(ii) What is the space complexity of a search usually measured in terms of?
(iii) What does it mean for a search to be complete?
(iv) What does it mean for a search to be optimal?
(b) The four searches in Question 2 are commonly referred to as uninformed searches. What does it mean to say that a search algorithm is uninformed?
(c) Of the four searches in Question 2, depth-first search with iterative deepening is usually considered the best. Discuss depth-first search with iterative deepening in terms of time complexity, space complexity, completeness, and optimality.
Page – 5
Question 4 [ 4 + 1 + 2 + 4 + 3 + 4 = 18 marks ]
Consider the following problem:
A man and a woman of equal weight, together with two children, each of half their weight, are all on the east of a crocodile infested river. They need to get to their car, which is on the west side. They have a boat which can only carry the weight of one adult. The boat cannot cross the river by itself, with no people on board. How can they use the boat to cross the river safely?
The problem is to be solved as a state space search problem, and this requires that a state representation scheme be devised.
(a) Devise a suitable state representation scheme for this problem. If you are representing a state as a list, then make sure that it is clear exactly what the elements of the list represent, and the values that they can take.
(b) Express the initial state using the representation that you described in (a).
(c) What is the smallest number of operators required under the representation you described in (a)? List these operators, giving each a descriptive name.
Page – 6
(d) Sketch the first three levels (i.e., root node plus next two levels) of the breadth-first search that would result from the use of these operators on this problem. Make sure that you indicate the state corresponding to each node, and the operators that have been applied to move from one state to another. Do not include illegal states, or states that have already been visited.
Page – 7
(e) Write LISP state constructor and accessor functions for the state representation that you have devised in (a).
(f) Write a LISP function implementing any one of the operators you identified in (c). Your function should take a state as input, and return the state resulting from applying that operator. You may assume that a helper function safe has already been written and tested. The function safe takes a state as input and returns that state if it is safe; otherwise it returns nil. You DO NOT need to write the function safe.
Page – 8
Question 5 [ 2 + 2 + 2 + 2 + 2 = 10 marks ]
A student wishes to use best-first search to solve a state space search problem. The function that she will use to order the states on the open list has the form f(n) = g(n) + h(n), where g(n) is the length of the path from the start state to state n, and h(n) is a heuristic estimate of the length of the path from state n to the goal state. The student is interested in comparing the performance of best-first search under four different heuristics: h1, h2, h3 and h4.
(a) When used in conjunction with heuristic h2, best-first search results in an admissible search. What does this mean?
(b) What property must a function h(n) possess in order for it to result in an admissible search?
(c) The student conducts an experiment in which she trials best-first search using a different one of the four heuristics on each trial. The table below shows the number of nodes examined in the search and the length of the solution path in each case. Each row corresponds to a different heuristic. You are given the following information:
• h4 assigns all nodes a value of 0 (i.e., h4(n) = 0 for all n)
• h2 is admissible
• h1 is more informed than h2, but not as informed as h3
Identify which row corresponds to which heuristic by placing h1, h2, h3 and h4 in the appropriate line of the table:
Heuristic
Number of nodes expanded
Length of solution path
40
17
60
12
140
12
50
14
Page – 9
(d) A fifth heuristic, h5, is now proposed. When tested on the above problem, it results in a solution of path length 12. What can you conclude about the admissibility of heuristic h5? You must provide a reason for your answer.
(e) Suppose that for a particular problem, it is important that the problem be solved as quickly as possibly (i.e., in the minimum amount of time). In addition to informedness, what other factor would be important in comparing the performance resulting from different heuristics?
Page – 10
Question 6 [ 1 + 5 + 2 + 2 = 10 marks ]
The figure below shows a portion of a search tree on the 8 puzzle problem. Each node is labelled. The start node is node A. The goal node is the state with a 1 in the upper left corner, with tiles ordered in ascending order as one moves clockwise around the perimeter of the puzzle board; i.e.,
A
BCD
1
2
8
6
3
7
5
4
1
2
8
6
3
7
5
4
1
2
8
6
3
7
5
4
1
6
2
8
3
7
5
4
(a) List the states that are currently on the OPEN list.
(b) Assuming that states on the OPEN list are ordered using a function of the form f(n) = g(n) + h(n), where g(n) is the length of the path from the start state to state n, and h(n) is the tiles-out- of-place heuristic, determine which node on the OPEN list will be the next one to be expanded. You will need to calculate the f value for all states on the OPEN list.
Page – 11
(c) On the diagram above, show the states resulting from expanding the node that you identified in (b).
(d) What will be the next node to be expanded? Show any additional working that you have performed, and explain why you have given this answer.
Page – 12
Question 7 [ 5 + 5 = 10 marks ]
The figure below shows a game tree as generated by the minimax algorithm. The numbers below the leaf nodes indicate the value of the heuristic applied to those leaf nodes.
MAX
A
36
B
43
6
59 25
(a) Assuming MAX is about to move, which move (i.e., A or B) will be chosen if minimax search
is used? (Show the propagated values on the game tree above)
(b) Alpha-beta search is a variation of the minimax algorithm in which evaluation of states is integrated with the generation of the tree. The figure below shows exactly the same tree as above. Place a cross through the leaf nodes that would NOT need to be evaluated if a left-to- right alpha-beta search were used.
A
36
B
43
6
MAX
59 25
Page – 13
Question 8 [ 2 + 2 + 2 + 2 = 8 marks ]
(a) What does it mean to say that an inference rule is complete?
(b) What does it mean to say that an inference rule is sound?
(c) Consider the following inference rule that infers P from P Q and P
PQ Q
P
Show using a truth table that this inference rule is NOT sound.
(d) Provide an example of an inference that IS sound, and use a truth table to demonstrate that it is sound.
Page – 14
Question 9 [ 2 + 2 + 3 + 3 = 10 marks ]
Convert the following sentences into Predicate Calculus expressions using only the following predicates, with the meaning indicated.
bicycle(X)
car(X)
blue(X)
rides(X,Y)
faster(X,Y)
has_2_wheels(X)
(a) Some bicycles are blue.
(b) All bicycles have two wheels.
(c) Cars are faster than bicycles.
(d) John only rides bicycles which are blue.
X is a bicycle X is a car
X is blue
X rides Y
X is faster than Y X has two wheels
Page – 15
Question 10
Consider the following:
Daffy has a big beak.
If something has a big beak, then it is a duck. Rabbits outsmart ducks.
Bugs is a rabbit.
Tweety is a bird.
(a) Provide predicate calculus expressions for the above information. You must use ONLY the following predicates and constants, with the meaning indicated. Show all quantifiers.
has_big_beak(X)
outsmarts(X,Y)
duck(X)
rabbit(X)
bird (X)
bugs
daffy
tweety
X has a big beak X out-smarts Y X is a duck
X is a rabbit
X is a bird Bugs Daffy Tweety
(b) Based on the expressions you wrote in (a), use backward chaining to prove that Bugs outsmarts Daffy.
[ 4 + 5 + 7 = 16 marks ]
Page – 16
(c) Now use resolution refutation to prove that Bugs outsmarts Daffy. Make sure that you show all steps, and the substitutions made at each step.
Page – 17
Question 11 [ 2 + 2 + 2 = 6 marks ]
In order to resolve two sentences that contain variables, appropriate unifications (i.e., substitutions) need to be made.
Show the most general substitutions that would make the expression
foo(X, bob, moo(Y))
identical to each of the following:
(a) foo(george, bob, moo(Z))
(b) foo(Z, bob, moo(goo(Z)))
(c) foo(W, bob, moo(jack))
Page – 18
Question 12 [ (3 + 3 + 4) + (3 + 1) = 14 marks]
(a) Consider the following facts, which are assumed to be in a PROLOG knowledge base:
% parent(Parent, Child) means Parent is parent of Child %
parent(elizabeth, charles).
parent(elizabeth, andrew).
parent(elizabeth, edward).
parent(elizabeth, anne).
parent(philip, charles).
parent(philip, andrew).
parent(philip, edward).
parent(philip, anne).
parent(charles, william).
parent(charles, harry).
parent(william, george).
parent(william, charlotte).
parent(william, louis).
parent(harry, archie).
parent(andrew, eugenie).
parent(andrew, beatrice).
% male(X) means X is male
%
male(philip).
male(charles).
male(andrew).
male(edward)
male(william).
male(louis).
male(george).
male(harry).
male(archie).
% female(X) means X is female
%
female(elizabeth)
female(anne)
female(eugenie).
female(beatrice).
female(charlotte)
% yearOfBirth(Person, Year) means yearOfBirth of Person is Year %
yearOfBirth(elizabeth, 1925).
yearOfBirth(philip, 1921).
yearOfBirth(charles, 1948).
yearOfBirth(anne, 1950).
yearOfBirth(andrew, 1960).
yearOfBirth(edward, 1964).
yearOfBirth(george, 2013).
yearOfBirth(louis, 2018).
yearOfBirth(william, 1982).
yearOfBirth(harry, 1984).
yearOfBirth(archie, 2019).
yearOfBirth(eugenie, 1990).
yearOfBirth(beatrice, 1988).
yearOfBirth(charlotte, 2015).
Page – 19
(i) Consider the following Prolog rule:
mystery(A,B) :-
parent(A,C),
parent(C,B),
female(B).
List, in correct order, all of the values returned by the following query:
?- mystery(elizabeth, X).
(ii) Write a procedure younger(Younger, Older), which is true if person Younger is younger than person Older. It should operate as follows:
?- younger(beatrice,eugenie).
false.
?- younger(eugenie,beatrice).
true.
Page – 20
(iii) Complete the following definition of a recursive procedure descendant. It should operate as follows:
?- descendant(charles,X).
X = william ;
X = harry ;
X = george ;
… and so on.
% descendant(Pers, Desc) means Desc is a descendant of Pers. %
% Base case
%
descendant(Pers, Desc) :-
% Recursive case
%
descendant(Pers, Desc) :-
(b) Consider the following PROLOG program for a procedure f1:
f1([],X,X).
f1([X|Y],Z,[X|W]) :- f1(Y,Z,W).
(i) What would returned by the following query:
?- f1([3,2], [4,5], M).
(ii) What would be a more appropriate descriptive name for this procedure?
Page – 21
Question 13 [ 5 + (4 + 1) = 10 marks ]
Suppose that the knowledge base in an expert system contains the following rules:
R1: IF FACT1 = true and FACT8 = true THEN GOAL3 = true R2: IF FACT2 = true THEN FACT6 = true
R3: IF FACT2 = true THEN FACT7 = true
R4: IF FACT3 = true and FACT6 = true THEN GOAL1 = true R5: IF FACT4 = true THEN FACT5 = true
R6: IF FACT4 = true and FACT3 = true THEN FACT8 = true R7: IF FACT4 = true and FACT7 = true THEN GOAL2 = true R8: IF FACT5 = true THEN FACT7 = true
(a) Assume the following:
• Forward-chaining is used.
• The truth values of Facts 1 to 4 are asserted into the facts knowledge base at the start of
the consultation as follows:
FACT 1: False FACT 3: False FACT 2: True FACT 4: True
• Conflict resolution is by lowest numbered rule.
• Rules fire only once.
• Chaining terminates when one of the goals has been asserted into working memory.
Complete the following table, showing the expert system’s operation until one of the goals has been found.
Cycle
Working Memory (before firing rule)
(Show only the facts which are True)
Conflict Set
Rule fired
1
F2, F4
2
3
4
5
6
7
Page – 22
(b) Assume the following:
(i)
(ii)
Which of GOAL1, GOAL2, or GOAL3, will be asserted at the end of the consultation?
• •
• • •
Backward-chaining is used.
Only Facts 1, 2, 3 and 4 are “askable”. When asked the truth of these askable facts the user will answer:
FACT 1: False FACT 3: True FACT 2: True FACT 4: False
Conflict resolution is by lowest numbered rule. Rules fire only once.
Inferencing stops when a goal has been found.
During the consultation the expert system will question the user about the truth of one or more facts. List each of these facts in the order in which the user is asked about them, explaining your reasoning.
Page – 23
Question 14 [ 8 marks ]
Consider the following semantic net which describes properties of birds and other animals.
Represent this information using a framed-based representation where each frame has three slots: is_a, travel, and covering. Your representation should show how a frame’s slot values are inherited from its superclass. Note that inherited values can be over-ridden.
Page – 24
Question 15 [ 4 + 4 = 8 marks ]
Predicate calculus and semantic networks are two of the most common knowledge representation schemes used in artificial intelligence. For each of the following two problems, identify which of predicate calculus or semantic networks would be the most appropriate knowledge representation scheme to use. You must provide a reason for your answer; i.e., describe what feature or features of this knowledge representation scheme makes it appropriate for this type of problem.
a) A vehicle classification domain, where you wanted to represent the relationships between various types of vehicles (e.g., boats, trucks, skateboards, flying saucers) and reason about their likely properties.
b) A blocksworld problem where a robot arm must determine the sequence of operations required in order to stack a set of blocks.
Page – 25
Question 16 [ 8 marks ]
Describe in pseudocode or otherwise the operation of the ID3 decision tree induction algorithm.
Page – 26
Question 17 [ 4 + (1 + 1) + 2 + 2 + 2 = 12 marks ]
Suppose that you have been given a dataset containing 40 instances, described over the following four attributes:
• pay_rate (pay rate in $ per hour)
• reputation (‘poor’, ‘fair’ or ‘good’)
• location (one of the following five region codes: 213, 172, 658, 279 and 100)
• success (‘yes’ or ‘no’).
Here are the first three rows of the dataset:
(a) For each of the four attributes, indicate whether it is ‘numeric ratio’, ‘numeric interval’, ‘categorical ordinal’, or ‘categorical nominal’. Underline the correct answer in each case. (Note that in some cases, more than one answer may be acceptable – you are only required to underline one answer in each case.)
i. pay_rate ( ratio / interval / ordinal / nominal ) ii. reputation ( ratio / interval / ordinal / nominal ) iii. location ( ratio / interval / ordinal / nominal ) iv. success ( ratio / interval / ordinal / nominal )
(b) You would like to implement a Multilayer Perceptron (MLP) model to predict the value of attribute success on the basis of the other three attributes. Answer each of the following questions.
(i) How many input nodes should be used?
(ii) How many output nodes should be used?
15
good
172
Yes
26
fair
213
No
12
poor
100
Yes
Page – 27
(c) Suppose that you test your model using a methodology where 75% of examples are used for training the MLP and 25% are used for testing, but you suspect that the estimated accuracy of the model is below what it would be if all 40 examples had been used for training. Describe an alternate methodology which would allow you to obtain a more accurate estimate of the accuracy of your model.
(d) Explain what is meant by ‘over-fitting’ in the context of classification tasks. (You may wish to use an example in your explanation).
(e) You have concluded that your MLP is overfitting the training data. Describe two things that you could change that might reduce the degree of overfitting. Make sure that you include the direction of change (i.e., increase or decrease).
Page – 28