QUESTION/ANSWER BOOKLET COMPSCI 367

Page 1 of 20

THE UNIVERSITY OF AUCKLAND


SEMESTER TWO 2018
Campus: City



COMPUTER SCIENCE


Artificial Intelligence




(Time Allowed: TWO hours)



NOTE:

This exam is out of 100 marks.
Attempt ALL questions.
Write your answers in the space provided in this booklet. There is space at the back for
answers that overflow the allotted space.
The use of calculators is NOT permitted.

Surname
Forenames
Student ID
Login (UPI)

Part Mark Marks Available
A 25
B 35
C 40
Total 100


QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 2 of 20














THIS PAGE HAS BEEN INTENTIONALLY LEFT BLANK.






QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 3 of 20
PART A: Yun Sing Koh’s material

Question 1

Explain and discuss the k-means clustering algorithm. You do not need to write code, but you
do need to give a precise description which someone could turn into code.
[8 marks]










































QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 4 of 20
Question 2

Explain the differences between the types of neural networks listed below. You may use
diagrams to support your explanations.
a) single-layered network (perceptron) versus multi-layered network,
b) feed-forward network versus recurrent network.
[8 marks]









































QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 5 of 20
Question 3

Consider the following customer purchase transaction dataset:

TID Items Purchased
1 A, B, C, G, H
2 B, C, D, E
3 C, D
4 A, B, D
5 A, B, C
6 E, F

TID represents the transaction ID. Assume that the minimum support threshold is set to 35%.
Identify all the closed frequent itemsets together with their support. Show your working.
[3 marks]


































QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 6 of 20
Question 4

The diagram below shows the error rate of a decision tree learner as the complexity of the tree
increases (number of nodes) on a training set and a test set. The test set is a dataset that is
independent of the training set, but follows the same probability distribution as the training set.
Using the diagram below, (i) highlight and label the area where the model is underfitting and
(ii) highlight and label the area where the model is overfitting. Explain why you think the
areas you highlighted are overfitting or underfitting the data.
[3 marks]

























QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 7 of 20
Question 5

You are a robot working for the Department of Conservation, and must learn to
discriminate bird types, specifically Kiwi from Morepork. You choose to learn a Naïve
Bayes classifier. You are given the following (noisy) examples:

Sound Fly Size Class
Quee No Large Kiwi
Cree Yes Large Kiwi
Cree No Small Kiwi
Cree No Small Kiwi
Quee Yes Large Morepork
Quee No Small Morepork
Cree Yes Small Morepork
Quee Yes Large Morepork


Now assume that the attributes (Sound, Fly, and Size) are conditionally independent of the
Class. Consider a new example (Sound=Cree, Fly=No, Size=Large), should we consider the
Class for this example as “Kiwi” or “Morepork”? Show your working. You may leave your
working as common fractions, e.g., 1/4, 3/5.
[3 marks]




























QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 8 of 20
PART B: Mike Barley’s material

Question 6

Using Prolog, write the definition of isTreeRoot(Node) where Node is a tree root if it does not
have a parent. You can only use childOf(Child, Parent) facts and built-in Prolog predicates
to write this definition. The allowable built-in predicates include: not(Pred), <, =, > and
is(Result, Expression).
[5 marks]


isTreeRoot(Node) :-


































QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 9 of 20
Question 7

Given the game tree below, use the minimax procedure to propagate the values up from the
leaves to the root. Label each of the six unlabelled internal nodes with their propagated
value.
[6 marks]





18 8 2 21 14 165
14 3 15 4 11 7
QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 10 of 20
Question 8

Assuming both A* and IDA* use the same heuristic and traverse the search space in the same
order, why would A* expand fewer nodes than IDA*? How could it be possible that IDA*
can solve the problem faster than A*?
[3 marks]
















Question 9

What performance trade-off is the goal in weighted A*? Which part of this trade-off is
guaranteed for weighted A* and which part is not guaranteed?
[3 marks]














QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 11 of 20
Question 10

As described in lectures, the goal for bidirectional heuristic search is to be better than which
two search algorithms? Up until this year, how successful has it been?
[3 marks]


















Question 11

What are the three different parts of a constraint satisfaction problem? What constitutes a
valid solution to a constraint satisfaction problem, i.e., what are the termination conditions?
[5 marks]



















QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 12 of 20
Question 12

As discussed in class, what is the heuristic for selecting a value for a given variable in a
constraint satisfaction problem? Giving its name is not sufficient for full marks, you need to
describe the procedure performed by the heuristic. What is this heuristic trying to
accomplish?
[5 marks]


















Question 13

What is arc consistency, i.e., describe how it works. What is the purpose of arc consistency?
What type of trade-off does it represent?
[5 marks]















QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 13 of 20
PART C: Ian Watson’s material

Question 14

Expert system shells allow knowledge engineers to concentrate on eliciting knowledge and
representing this as rules, without having to trouble themselves with programming
inferencing methods. Draw a diagram which shows the architecture of a typical expert system
shell and shows how each of the components interacts with each other and with the user.
[5 marks]







































QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 14 of 20
Question 15

Draw a diagram that describes the steps involved in Case-Based Reasoning (CBR).
[5 marks]











































QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 15 of 20
Question 16

A major constraint on developing knowledge-based systems is the knowledge engineering
bottleneck, caused by the difficulty of eliciting knowledge from domain experts. Describe
three potential solutions to this bottleneck that you have learned from COMPSCI367.
[10 marks]










































QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 16 of 20
Question 17

You have been asked to build a knowledge-based system to provide valuations for a second-
hand boat dealership. You visit the dealership and obtain the following transcript of a
conversation with an experienced salesman.

“Well obviously the most important thing that influences the price is the type of boat and its
size. The larger the boat the more expensive it is in general. The age of the boat is important
and of course its condition matters. Older aluminium boats tend to hold their price better
than older fibreglass ones. Then of course there is the engine. Its make, horsepower and age
is important, but you also have to consider how much the engine has been used, and how
often it has been serviced. Then there are all the extras: the electronics, like fish-finders,
GPS, and VHF radio. The model, age and condition of these is important as well. Then
there’s all the other equipment like anchors, chain and rope, safety equipment: like life-
jackets, distress beacons, flares etc....Finally there are all the toys like skis and fishing
equipment. So as you can see there’s a lot that can influence the price of a boat. Oh, I forgot
to mention the trailer, the type, age and condition of that is very important as well. Sorry, I
also forgot finance, we’ll drop the price if someone wants finance because we can make
money from the finance package.”

Analyse this transcript and draw an inference network or influence diagram to create a
knowledge level model of the factors that effect the sale price of a boat.

[Hint: use an overflow page at the back of the exam paper to work out your answer and then
copy your final version to the space on the next page.]

























QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 17 of 20
[10 marks]
















































QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 18 of 20
Question 18

Why would people develop ontologies for domains such as medicine, law or engineering?
Your answer should discuss some of the advantages of using ontologies in complex domains.
[10 marks]












































QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 19 of 20


OVERFLOW PAGE
This page was left blank for any questions that overflow.
(If you have used this page, please indicate clearly under the
relevant question that you have overflowed to this page.)












































QUESTION/ANSWER BOOKLET COMPSCI 367
ID: …………………………
Page 20 of 20


OVERFLOW PAGE
This page was left blank for any questions that overflow.
(If you have used this page, please indicate clearly under the
relevant question that you have overflowed to this page.)

































































































































































































































































































































































































































































































































































































































































































































































































































































































































































学霸联盟