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.

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

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.