## 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.