VERSION 00000001 COMPSCI367
THE UNIVERSITY OF AUCKLAND
SECOND SEMESTER 2019 Campus: City
COMPUTER SCIENCE Artificial Intelligence
(Time Allowed: TWO hours)
This exam is out of 60 marks.
Attempt ALL questions.
For questions in part A, please enter your answers in the provided teleform sheet and for the questions in parts B and C, please 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)
A 26 B 14 C 20
Marks Available
Page 1 of 17
VERSION 00000001 COMPSCI367
THIS PAGE HAS BEEN INTENTIONALLY LEFT BLANK.
Page 2 of 17
VERSION 00000001 COMPSCI367 Question/Answer Sheet ID ………………….
PART A: MULTIPLE CHOICE QUESTIONS
Question 1
[2 marks] In what decade was the model of artificial neurons first published?
(a) 1940s (b) 1950s (c) 1980s (d) 1960s (e) 1970s
Question 2
[2 marks] Which of the following is an example of a general purpose problem solving method?
(a) Retrieve and rationalize (b) Hypothesise and review (c) Generate and test
(d) Test and apply
(e) Lucky dip
Question 3
[2 marks] Which of the following is part of an expert system shell architecture?
(a) Inference engine (b) Case-base
(c) Data-base
(d) Decision table (e) Decision tree
Question 4
[2 marks] What is control knowledge also called?
(a) Micro-knowledge (b) Heuristic knowledge (c) Meta-knowledge
(d) Process knowledge (e) Mega-knowledge
Question 5
[2 marks] When should you NOT apply an expert system or knowledge-based system?
(a) When knowledge is dynamic
(b) When knowledge is critical
(c) When the problem needs to be better understood (d) When knowledge is rare
(e) When knowledge is valuable
Page 3 of 17
VERSION 00000001 COMPSCI367 Question/Answer Sheet ID ………………….
Question 6
[2 marks] What type of inferencing method is most appropriate for diagnostic problems?
(a) Heuristic search
(b) Breadth-first search (c) Data-driven search (d) Backward chaining (e) Forward chaining
Question 7
[2 marks] What CLIPS command would you use to remove all facts, templates, rules, and functions from the memory?
(a) erase (b) clean (c) clear (d) wipe (e) remove
Question 8
[2 marks] Which is the correct sequence of knowledge engineering activities for building a knowledge-based system?
(a) Elicitation, Analysis, Acquisition, Representation (b) Analysis, Elicitation, Acquisition, Representation (c) Representation, Analysis, Elicitation, Acquisition (d) Elicitation, Acquisition, Analysis, Representation (e) Analysis, Elicitation, Acquisition, Representation
Question 9
[2 marks] Translate the following predicate calculus statement into English: “X(basketball_player(X)Þ tall(X))
(a) There are tall basketball players (b) All basketball players are tall (c) If X is tall they play basketball (d) Basketball player X is tall
(e) There exists a basketball player X who is tall
Page 4 of 17
VERSION 00000001 COMPSCI367 Question/Answer Sheet ID ………………….
Question 10
[2 marks] Translate the following predicate calculus statement into the Conceptual Graph linear form (LF).
($x:Cat)($y:Mat)on(x,y)
(a) [Cat]->(On)->[Mat]
(b) Cat(x)-On-Mat(y)
(c) Cat-On-Mat
(d) [Cat]-(On)-[Mat]
(e) (exists ((?x Cat) (?y Mat)) (On ?x ?y))
Question 11
[2 marks] Which of the following is the correct order of processes in the CBR-cycle?
(a) Reuse, Repair, Retrieve, Retain (b) Retrieve, Reuse, Repair, Retain (c) Retain, Retrieve, Reuse, Repair (d) Retrieve, Repair, Reuse, Retain (e) Retain, Repair, Retrieve, Reuse
Question 12
[2 marks] Why can CBR be said to be “transparent”?
(a) Because CBR systems can learn by example.
(b) Because CBR is clear and simple.
(c) Because features in a case can be weighted.
(d) Because cases can be seen in a case-base.
(e) Because precedent is an accepted method for justifying a decision made by a CBR system.
Question 13
[2 marks] How do CBR systems learn?
(a) By inferring rules from cases in the case-base. (b) By retaining new cases in the case-base.
(c) By refining the case-base and editing cases. (d) By learning new feature weights for the cases. (e) CBR systems cannot learn.
Page 5 of 17
VERSION 00000001 Question/Answer Sheet
Question 14
COMPSCI367 ID ………………….
PART B: ’s material
Please draw the backward chaining tree (like prolog) which would prove the following goal: easter-bunny(W), given the following rules:
rabbit(X) Ù has(X,Y) Ù chocolate-egg(Y) Ù time(easter) Ù mythical(X) Þ easter-bunny(X) turkey(Y) Ù is-fat(Y) Ù time(thanks-giving) Þ tom-turkey(Y)
fairy-story(Z) Ú childrens-story(Z) Þ mythical(Z) and facts:
has(fred,sam)
chocolate-egg(sam)
childrens-story(fred) rabbit(fred) turkey(fred) is-fat(sam) time(easter)
Page 6 of 17
VERSION 00000001 COMPSCI367 Question/Answer Sheet ID ………………….
Question 15
Please fill in the chart below. You will only get full marks for explaining “why” and under what assumptions an algorithm is optimal or is complete!
Iterative Deepening Breath First Depth First
Is it optimal?
Is it complete?
Page 7 of 17
VERSION 00000001 COMPSCI367 Question/Answer Sheet ID ………………….
Question 16
Please describe the basic technique of simulated annealing and when and why it might be
better than random restart hill-climbing?
Page 8 of 17
VERSION 00000001 Question/Answer Sheet
Question 17
COMPSCI367 ID ………………….
Question 18
Informed Search
PART C: ’s material
The Assignment
What was the goal state for assignment A4 (Domain-independent planning)? Assume the tour begins and ends at city A, write the goal state exactly as it would appear in our assignment’s problem description.
A. Does greedy search try to find a solution as quickly as possible or try to find as cheap a solution as possible? Is greedy search guaranteed to achieve this? For full marks, explain why or why not.
B. Does A* try to find a solution as quickly as possible or try to find as cheap a solution as possible? Is A* guaranteed to achieve this? For full marks, explain why or why not.
Page 9 of 17
VERSION 00000001 COMPSCI367 Question/Answer Sheet ID ………………….
Question 19
A. Give the formula for f(n) for both weighted A* and A*.
B. In our lectures, 2 possible reasons were given for why weighted A* might be able to expand so many fewer nodes than A*. Give one of them.
Page 10 of 17
VERSION 00000001 COMPSCI367 Question/Answer Sheet ID ………………….
Question 20
A. In this course, what condition indicates that a solution path has been found in bidirectional search? Define this condition appropriately in terms of direction and node membership in open and closed lists.
B. What is the difference between a front-to-front heuristic and a front-to-back heuristic? Which is most commonly used in today’s bidirectional heuristic search algorithms?
Page 11 of 17
VERSION 00000001 COMPSCI367 Question/Answer Sheet ID ………………….
Question 21
Given heuristics h1 and h2, name two conditions for adding them, e.g., h(n) = h1(n) + h2(n), that are necessary to guarantee their sum is admissible?
Question 22
A. For a planning problem P, what does it mean for X to be a solution to P.
Page 12 of 17
VERSION 00000001 COMPSCI367 Question/Answer Sheet ID ………………….
B. In our representation of progression planning, can an operator have a static predicate in its effects? How about in its preconditions? For full marks, explain why in both cases.
Question 23
In our lectures on modelling domains for planning problems, I discussed 4 languages that were used to describe states, operators, and problems. Prolog and the state language are two of them and they are used to write metaLevel predicates for operator preconditions and to represent states, respectively. Name the two remaining languages and for full marks say what they are used for.
Page 13 of 17
VERSION 00000001 Question/Answer Sheet
Question 24
COMPSCI367 ID ………………….
Constraint Satisfaction Problems
A. What are the three components of a constraint satisfaction problem? What would be examples of those components for the 4-queens problem?
B. For a constraint satisfaction problem P, in terms of those three components what does it mean for X to be a solution to P.
Page 14 of 17
VERSION 00000001 COMPSCI367 Question/Answer Sheet ID ………………….
Question 25
What is the most-constrained variable heuristic? Why does it decrease the probability of
having to backtrack?
Page 15 of 17
VERSION 00000001 Question/Answer Sheet
COMPSCI367 ID ………………….
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.)
OVERFLOW PAGE
This page was left blank for any questions that overflow. Page 16 of 17
VERSION 00000001 COMPSCI367 Question/Answer Sheet ID ………………….
(If you have used this page, please indicate clearly under the relevant question that you have overflowed to this page.)
Page 17 of 17