## Artificial Intelligence Final Exam : May 1996

### Problem 1:

(15 points)
Give an example of an English text that has a potential anaphoric ambiguity
that can be resolved using selectional restrictions. Explain the
selectional restriction used.
### Problem 2:

(20 points)
Consider the following problem: You have a collection of blocks, and you
wish to stack them one on top of another to make as tall a tower as possible.
However, the blocks are oddly shaped, so not every block will fit on top of
every other block. For instance, you might know that block A will fit on
blocks D, E, and F; that block B will fit on top of A, C, D,; that
C will fit on A, D and E; that D will fit on C and E; that E fits on A and D;
and that F does not fit on any block. Then the tallest tower has height 5;
for example, A, E, D, C, B. It is not possible to build a block using all
6 blocks.
- A. Show how to use state space search to solve this problem. In
particular, you should specify (i) What is a state? (ii) What is an
operator? (iii) What is the start state? (iv) What is the objective
of the search?
- B. What search technique would you use to solve this problem?
Give an upper bound on the required time and space.

### Problem 3:

(10 points)
In the MAX-MIN tree shown below, for what values of node X can node Y
be pruned?

### Problem 4:

(10 points)
Name three conditions that must hold on a game for the technique of MIN-MAX
game-tree evaluation to be applicable.
### Problem 5:

(10 points)
Give an example of a Prolog program and a query that never returns an answer
if the
interpreter uses a depth-first search (as Prolog does), but that will
return an answer if the interpreter is modified to use an iterative
deepening search. (Hint: there is an example that uses one rule and one fact.)
### Problem 6:

(5 points)
Which of the following describes the process of task execution
(classifying input signal) in a feed-forward, back-propagation neural network?
Which describe the process of learning? (One answer is correct for each.)
- a. Activation levels are propagated from the inputs through the hidden
layers to the outputs.
- b. Activation levels are propagated from the outputs through the hidden
layers to the inputs.
- c. Weights on the links are modified based on messages propagated
from input to output.
- d. Weights on the links are modified based on messages propagated
from output to input.
- e. Connections in the network are modified, gradually shortening
the path from input to output.
- f. Weights at the input level are compared to the weights at the
output level, and modified to reduce the discrepancy.

### Problem 7:

(10 points)
Explain briefly (2 or 3 sentences) the use of a training
set and a test set in evaluating learning programs.
### Problem 8:

(10 points)
Let H be a hypothesis in the set S (of too specialized
hypotheses) in the candidate elimination algorithm. What does the algorithm
do if H gives a false positive on some input example? What does the
algorithm do if H gives a false negative?
### Problem 9:

(10 points)
Describe briefly two ways in which texture can be used in vision
systems.