Artificial Intelligence: Final Exam May 1996
Take home exam
Due Friday, May 10 10:00 AM
Email: davise@cs.nyu.edu
Hard copy: Slide under door of Warren Weaver, 429
Fax: 995-4121
Problem 1: (20 points)
Consider the following sentences:
i. Cats and dogs are animals.
ii. Everyone in this room either owns a cat or owns a dog.
iii. Anyone who owns an animal has a friend.
iv. Everyone in this room has a friend.
Let L be a first-order language containing the following predicates:
c(X) --- X is a cat.
d(X) --- X is a dog.
a(X) --- X is an animal.
o(X,Y) --- X owns Y.
r(X) --- X is in the room.
f(X,Y) --- X is a friend of Y.`
A. State each of the sentences (i) -- (iv) in L.
B. Show that (iv) can be proven from (i) -- (iii) using resolution.
You should show the Skolemized form of all the clauses involved and each
step of the resolution proof. You need not show the intermediate steps of
Skolemization.
Problem 2: (15 points)
The K-CLIQUE problem is defined as follows: Given an undirected graph G
and an integer K, find a set S of K vertices in G such that any pair of
vertices in S is connected by an edge in G.
For instance, if the vertices are people, and there is an arc connecting
I and J if persons I and J are acquainted, the problem is that of forming
a party of K people where everyone knows one another.
We wish to find a search technique for solving K-CLIQUE that is guaranteed
to find an answer if one exists.
A. Describe a suitable search space. In particular, you should state (a)
what are the states; (b) what are the operators; (c) what is the start
state; (d) what are the goal states.
B. What is the maximal branching factor in your state space?
C. Is your state space systematic (tree-structured)? If not, can you
modify it to be systematic?
D. What search technique would you use to search the space? Give some
simple easy upper bounds on the time and space requirement of this
search technique.
Problem 3: (10 points)
Consider the following variant of chess: On a player's turn, he does not
make a single move. Rather, he suggests two possible alternative moves,
and his opponent may choose between those two. (If there is only one
legal move, then that move is made.)
A. How would the process of game tree evaluation be modified for this
new game?
B. There is an analogue of alpha-beta pruning that can be applied to this
new game. Give an example of a game tree where pruning is possible.
(You need not give the general rule.)
Problem 4: (10 points)
Let L be a first-order language where terms take integer values containing
the following primitives:
3, 6 : Constants
s(X) : Function -- the successor of X
less(X,Y) : Predicate -- X is less than Y.
Consider the following two rules
i. forall(X,Y) less(X,Y) implies less(X,s(Y)).
ii. forall(X,Y) less(s(X),Y) implies less(X,Y).
Given the fact "less(s(3),6)" you wish to prove "less(3,s(6))"
A. Show how this inference can be carried out using backward chaining.
B. Show how this inference can be carried out using forward chaining.
C. In a system of directed inference, where each rule can be tagged either
to be used in forward chaining or to be used in backward chaining, how
should the two rules (i) and (ii) be tagged? Why?
Problem 5: (10 points)
A. Construct a multi-layer, feed-forward neural network to carry
out the following: There are four input cells. An input signal has an
activation level of 1 or 0 at each input cell. We want the neural network
to recognize signals with exactly two 1's and two 0's in input.
B. Prove that no single perceptron can carry out this task.
Problem 6: (Open-ended) (15 points)
The logical structure of kinship relations can be complex. For instance:
X is a step-brother of Y if X is male and one of X's parents is married to
one of Y's parents, but X and Y do not have a common parent.
X is a sister-in-law of Y if X is female and either
(a) X is a sibling of the spouse of Y;
(b) X is the spouse of a sibling of Y;
(c) X is the spouse of a sibling of the spouse of Y.
"ancestor" is the transitive closure of "parent"
X is the kth cousin m times removed of Y if either
some (k+1)st level ancestor of X is a (k+m+1)st level ancestor of Y
or vice versa.
Suppose you had the task of writing a program to learn the meaning of
kinship terms in some unknown society. How would you set up the inductive
bias for the program? Assume that the input is given in the form
of a large family tree --- that is, a database showing all parenthood
and all marriage relations, and the sex of each individual --- and a series of
triples of the form < person, person, relation> (e.g. ).
Problem 7: (20 points)
Consider the following variation on the blocks world. Blocks are rectangular
and may be placed either vertically or horizontally. Blocks oriented the same
way can be stacked, and a vertical block can be placed on top of a horizontal
block, but a horizontal block cannot be placed on a vertical block.
A block can be rotated to switch its orientation, but only if it is clear and
if it is on top of some other block (not if it is on the table).
As usual, the table has infinite capacity, and a block at
the top of one stack can be moved to the top of another stack, as long as the
orientations don't conflict.
A. How can this world be characterized in the STRIPS representation?
B. Show how POP can solve the following problem: From the starting
state shown below, attain the goal "on(B,A)".
___
| |
| |
|A|
__________ | |
|____B_____| |_|
________________________________
| |
| |
| Table |
| |