Question 1 [ 5 + 5 + 2 + 3 + 3 = 18 marks ]
(a) The surface area of a solid cylinder of end radius r and length l is given by: Surface Area = 2r(r + l)
Write a Lisp function cylsurf that takes two arguments, radius and length, and returns the surface area of the cylinder (using = 3.142).
(b) Write a Lisp function smallest that takes a list of numbers as its argument, and returns the smallest element of the list.
(c) The Lisp built in function mapcar is often referred to as a ‘higher order function’. What is meant by ‘higher order function’ in this context?
Page – 2
(d) What would be returned by the following?
> (mapcar (lambda (x) (+ (* x x) 1)) ‘(3 5 1 0))
(e) Consider the mystery function, defined as follows:
(defun mystery (L)
(if (null L)
nil
(if (evenp (first L))
(first L)
(mystery (rest L)))))
What would be returned by the following? > (mystery (list 1 5 6 3 4 7 8))
Page – 3
Question 2 [ 2 + 2 + 2 + 2 = 8 marks ]
Below is a tree structure that contains 21 nodes. Node A is the start node. Nodes J and P are both goal nodes.
A
BCDE
FGH IJKLMN
O PQRST
U
Write down, in sequential order, the nodes which are visited when conducting each of the following searches. Stop when either goal is found.
(a) breadth-first search
(b) depth-first search
(c) depth-first search with iterative deepening
(d) depth-first search with a depth limit of 2. (Node A is at depth 0)
Page – 4
Question 3 [ 2 + 2 + 2 + (2 + 2) = 10 marks ]
Breadth-first search, depth-first search, and best-first search are three well-known search algorithms.
(a) Breadth-first search and Depth-first search are uninformed search strategies, while best-first search is an informed search strategy. How do informed search strategies differ from uninformed search strategies?
(b) In best-first search, a function commonly used to rank nodes on the open list has the form f(n) = g(n) + h(n) , where g(n) is the distance from the start state to state n (i.e., the number of moves required to move from start state to state n). What does the function h(n) represent?
(c) What requirement must be satisfied in order that best-first search, used with a function of the form f(n) = g(n) + h(n) , results in an admissible search.
(d) Suppose that two algorithms—Algorithm A and Algorithm B—are to be used to search the tree given in Question 2. Algorithm A is admissible. Algorithm B is NOT admissible.
Circle the
i. Using A. B. C.
ii. Using A. B. C.
correct alternative in each of the following cases.
Algorithm A
Goal J will be found before goal P
Goal P will be found before goal J
Without further information it is not possible to determine which goal will be found first
Algorithm B
Goal J will be found before goal P Goal P will be found before goal J
Without further information it is not possible to determine which goal will be found first
Page – 5
Question 4 [ 8 marks ]
Complete the following table. Use Yes/No to indicate whether the algorithm is complete and optimal. Describe the time and space complexity expressed in terms of b (branching factor) and d (depth of solution).
Breadth-first search
Depth-first search
Depth-first search with iterative deepening
A-star search using an admissible heuristic
Complete? [Yes/No]
Optimal? [Yes/No]
Time complexity [O(?)]
Space complexity [O(?)]
Page – 6
Question 5 [ 10 marks ]
The ‘5-puzzle’ problem is a variation of the ‘8-puzzle’ problem in which there are only 5 tiles that can be moved. The goal state is:
goal state
Using the number of tiles out of place heuristic, and assuming that the operators are applied in the order Left, Right, Up, Down, show the operation of A* search on this problem, given the following start state:
start state
Your answer should clearly show:
(i) The order of expansion of the nodes.
(ii) The value of the function f(n) = g(n) + h(n) for each node that is generated.
If you would like more space, you can begin your answer on the next page.
1
2
3
4
5
1
2
5
3
4
Page – 7
Page – 8
Question 6 [ 5 + 5 = 10 marks ]
Two players, MIN and MAX, are playing a two-person game. It is MAX’s turn to make a move. She has two choices. 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.
(a) On the diagram, show the result of propagating the leaf values up the graph, all the way to the root (you should have a number next to each node), and use this information to show which decision would be made by MAX
(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 be evaluated if a left-to-right alpha-beta search were used.
Page – 9
Question 7 [ 2 + 2 + 3 + 3 + 2 + 2 = 14 marks ]
(a) What does it mean to say that an inference rule is sound?
(b) What does it mean to say that an inference rule is complete?
(c) The inference rule Modus Tollens can be used to infer P from P Q and Q. That is, PQ
Q P
Is Modus Tollens sound? Justify your answer using a truth table.
(d) Consider the following inference rule that infers R from R S and S
RS S
R
Is this inference rule sound? Justify your answer using a truth table.
Page – 10
(e) Describe the inference rule Modus Ponens by expressing it in the form given in (c) and (d) above.
(f) Is Modus Ponens complete?
Page – 11
Question 8 [ 2 + 2 + 3 + 3 = 10 marks ]
Convert the following sentences into Predicate Calculus expressions using only the following predicates, with the meaning indicated.
bike(X)
car(X)
faster(X,Y)
has_motor(X)
vehicle(X)
(a) All cars have a motor.
(b) Some bikes have a motor.
(c) Cars and bikes are vehicles.
X is a bike
X is a car
X is faster than Y X has a motor
X has a vehicle
(d) Vehicles that have a motor are faster than vehicles that do not have a motor.
Page – 12
Question 9 [ 6 + 8 = 14 marks ]
Consider the following:
It is a crime to sell an unregistered gun. Bugsy has several unregistered guns, and all of them were purchased from Squizzy.
Using the following predicates
sells(X,Y,Z) gun(X) unreg(X) criminal(X) owns(X,Y)
X sells Y to Z
X is a gun
X is unregistered X is a criminal
X owns Y
the above information can be expressed as follows:
XYZ unreg(Y) gun(Y) sells(X, Y, Z) criminal(X)
X unreg(X) gun(X) owns(bugsy, X)
X unreg(X) gun(X) owns(bugsy, X) sells(squizzy, X, bugsy)
(a) Convert the predicate calculus expressions above into clause form.
Page – 13
(b) Using resolution refutation, prove that Squizzy is a criminal. At each step, make sure that you show which sentences are being resolved, and under which subsitutions. You may set your proof out in either sequence or tree form.
Page – 14
Question 10 [ 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, a, goo(Y))
identical to each of the following:
(a) foo(fred, a, goo(Z))
(b) foo(W, a, goo(jack))
(c) foo(Z, a, goo(moo(Z)))
Page – 15
Question 11 [ 4 + 4 + 4 = 12 marks ]
(a) For the following Prolog program, state, in correct order, all the solutions that would be returned to the given query.
animal(zazu).
animal(leo).
aeroplane(jumbo).
aeroplane(concorde).
has_feathers(tweety).
has_feathers(zazu).
on(fred, concorde).
on(jim, intercity_express).
train(intercity_express).
bird(tweety).
bird(X) :- animal(X), has_feathers(X).
flies(X) :- aeroplane(X).
flies(X) :- bird(X).
flies(X) :- on(X, Y), aeroplane(Y).
?- flies(X).
(b) Consider the following facts, which are assumed to be in a Prolog knowledge base:
on_top_of(prolog_book, desk).
on_top_of(ai_notes, prolog_book).
on_top_of(time_table, ai_notes).
on_top_of(ai_book, desk).
Write a Prolog procedure above(X,Y), which is true if X is located above Y. It should operate as follows:
?- above(time_table, X).
X = ai_notes ;
X = prolog_book ;
X = desk ;
No ?-
Page – 16
(c) Write a Prolog procedure length(List,N), which is true if N is the number of items in List. It should operate as follows:
?- length([fred, barney, wilma], X).
X = 3.
?- length([], X).
X = 0.
Page – 17
Question 12 [ 6 + 6 = 12 marks ]
(a) Describe the Production System model of computation. In your response, make sure that you refer to production rules, working-memory and the recognize-act control cycle.
(b) The Production System model has several advantages over the logic-based models such as that implemented in the Prolog computer-programming language. Describe two of these advantages.
Page – 18
Question 13 [ 4 + 4 + 4 = 12 marks ]
Consider an expert system which contains the following rules:
R1: IF a person’s annual income is at least $40,000
AND the person’s highest level of education is a college degree THEN the person is recommended to invest in a growth stock.
R2: IF a person has at least $10,000 available to invest
AND the person’s highest level of education is a university degree THEN the person is recommended to invest in securities.
R3: IF a person is younger than 30
AND the person is recommended to invest in securities THEN the person is recommended to invest in a growth stock.
R4: IF a person is recommended to invest in a growth stock, THEN recommendation is Invest in IBM shares.
Only the following questions are askable (i.e., these are the only questions that the user can be asked):
A. What is your age?
B. What is your highest level of education?
C. How much do you have available to invest?
D. What is your annual income?
[27 years old] [university degree] [$15,000] [$30,000]
The entries in brackets indicate the user’s response, if asked that question.
(a) Consider a consultation in which backward chaining is to be used to establish the goal ‘Invest in IBM shares’. Which questions will the user be asked, and in what order? Explain clearly how you arrived at your answer.
Page – 19
(b) Now assume forward-chaining, and suppose that the system was provided the following information on a client:
Age:
Educational Level: Amount available to invest: Annual income:
State the order of rule firing.
27 Years old university degree $15,000
$30,000
(c) In the context of expert systems, what is meant by conflict resolution? Identify one common conflict resolution strategy, and describe the effect that it has on the line of reasoning.
Page – 20
Question 14 [ 3 + 3 + 6 = 12 marks ]
Consider the following knowledge about blood vessels:
• An artery is a kind of blood vessel.
• An artery always has a muscular wall, and generally has a diameter of 0.4cm.
• Blood vessels all have tubular form and contain blood.
• A vein is a kind of blood vessel, but has a fibrous wall.
• The aorta is a particular kind of artery which has a diameter of 2.5cm.
(a) Which type of knowledge representation scheme do you think is more appropriate for this knowledge: predicate calculus or semantic networks? You must provide a reason for your answer.
(b) Describe one advantage that frame-based semantic networks have over semantic networks that do not use frames?
Page – 21
(c) Represent the above knowledge using a frame-based semantic network. Make sure that you include the links between frames, and that you identify the types of those links.
Page – 22
Question 15 [ (1 + 3) + (1 + 2) + 2 + 3 = 12 marks ]
Suppose that you had a dataset showing the age, transmission type, number of cylinders, and fuel consumption for 250 cars. In the dataset, Age is a numeric variable, and represents the number of years since the vehicle was built; Transmission is a binary varaiable, and describes whether the vehicle is a manual or automatic; Cylinders is a discrete variable that describes the number of cylinders that the vehicle has, which can be either 4, 6 or 8; and Fuel Consumption is a numeric variable that describes the number of litres consumed for each 100 kilometres of travel.
Data for four of the vehicles is shown in the table below.
You are required to design a Multilayer Perceptron (MLP) to predict the value of Income on the basis of the other three attributes.
(a) Consider the problem of predicting Fuel Consumption on the basis of the other three variables.
i. Is this problem a classification problem or a regression problem?
ii. Suppose that you have chosen to use a neural network with a single hidden layer that contains three units. Draw a diagram showing the architecture of the network. Make sure that your sketch clearly indicates how many inputs and how many outputs your MLP has, and what data will be presented at each of those inputs. (You do not need to consider the activation functions that would be used at the hidden and output nodes).
Age
Transmission
Cylinders
Fuel Consumption
5
Manual
4-cyl
3
2
Automatic
6-cyl
4.5
25
Manual
8-cyl
12
10
Automatic
4-cyl
5
Page – 23
(b) Now consider the problem of predicting Cylinders on the basis of the other three variables.
i. Is this problem a classification problem or a regression problem?
ii. Suppose that you have chosen to use a neural network with a single hidden layer that contains three units. Draw a diagram showing the architecture of the network. Make sure that your sketch clearly indicates how many inputs and how many outputs your MLP has, and what data will be presented at each of those inputs. (You do not need to consider the activation functions that would be used at the hidden and output nodes).
(c) Neural networks are susceptible to overfitting. Define ‘overfitting’.
Page – 24
(d) One way of preventing overfitting is to monitor training error on a training set and a test set. Sketch the typical curves that would be expected when training error and test error are plotted against training time. On your sketch, show the point at which training should be stopped in order to avoid overfitting.
Page – 25
Question 16 [ 6 + 6 = 12 marks ]
The table below contains 13 examples described over five attributes. The objective is to develop a decision tree model to predict RISK on the basis of the other four attributes.
(a) Complete the following decision tree so that it classifies all 13 examples correctly. (There may be more than one possible tree that can correctly classify all examples correctly.)
Page – 26
(b) Describe in pseudocode or otherwise the operation of the ID3 decision tree induction algorithm.
Page – 27