-- draft --

AI Final Review Questions

The following questions are provided as an aid to preparing for the final exam. The scope of the final exam will vary from year to year, so this list may include some questions on material that we did not cover. If you are in doubt about whether or not you should know something the safest and best strategy to use is to go ahead and learn it. Just think of how much you will end up knowing. You can also check with the TA or instructor.

The exam is cumulative, covering the material from the entire course. Roughly 1/4 of the exam will be drawn from the first half of the course, and the other 3/4 will be drawn from the second half.

Topics covered in the midterm exam

Be sure to review the topics covered in the midterm exam, e.g., Prolog, search and games.


Answer the following true/false questions:



Describe the main differences between propositional logic and first order logic.

Give two propositional logic sentences that are equivalent to P Þ Q.

Modeling in logic

Translate the following statements into a FOPC sentence, choosing appropriate predicates and functions: (a) ``Good food is not cheap and cheap food is not good.''; (b) ``If a computer can beat Kasparov in chess, then a computer can beat anyone''. Rewrite your FOPC sentence as a set of sentences in conjunctive normal form and in implicative normal form.

Evaluating sentences

For each of the following sentences, say whether it is valid, unsatisfiable or either. Verify your assessment using either truth tables or by applying tautologies.

  • smoke => smoke
  • smoke => fire
  • (smoke => fire) => (~smoke => ~fire)
  • smoke V fire V ~fire
  • (smoke ^ heat) => fire <=> ((smoke => fire) V (heat => fire))
  • (smoke => fire) => ((smoke ^ heat) => fire)


Consider the four standard binary connectives used in logic: and, or, implies, iff. (a) How many possible binary connectives can we define? (b) give an example of two others which might be useful.

Evaluating sentences

Classify the following sentences as valid, satisfiable or unsatisfiable:

  1. " x P(x) Þ $ x P(x)
  2. $ x $ y ~Q(x,y) | P(x) Þ Q(x, y)
  3. " x P(x)


For each of the following pairs of predicates, determine if they unify. If so, show the resulting substitution.

  1. P(x, y, z) P(A, f(x), f(x))
  2. P(y, g(x), h(x)) P(f(u,v), u, h(v)
  3. P(f(x),x) P(y,f(y))
  4. Loves(Lover(x), Monica) Loves(Bill, Monica)
  5. Rel(Loves, x, x) Rel(Loves, Lover(y), y)
  6. P(x, f(A,B), y) P(u, f(u, v), u)

Modeling in logic

Consider a domain where the individuals are people and languages. Let L be the first-order language with the following primitives:
s(X,L) --- Person X speaks language L. 
c(X,Y) --- Persons X and Y can communicate. 
i(W,X,Y) --- Person W can serve as an interpreter between persons X and Y. 
j,p,e,f --- Constants: Joe, Pierre, English, and French respectively.
Express the following statements in L:
  • i. Joe speaks English.
  • ii Pierre speaks French.
  • iii. If X and Y both speak L, then X and Y can communicate.
  • iv. If W can communicate both with X and with Y, then W can serve as an interpreter between X and Y.
  • v. For any two languages L and M, there is someone who speaks both L and M.
  • vi. There is someone who can interpret between Joe and Pierre.

Show that (vi) can be proven from (i)---(v) using backward-chaining resolution. You must show the Skolemized form of each statement, and every resolution that is used in the final proof. You need not show the intermediate stages of Skolemization, or show resolutions that are not used in the final proof.

Resolution theorem proving

Use resolution to prove $ v P(A,v)&Q(A) given the following sentences. Express your proof as a resolution graph, and show substitutions.

  • " x Q(x) | S(x)
  • " y ~S(y) | T(B)
  • " z,w ~T(z) | P(w,z)

Game theory

Prisoner's dilemma

What constraints have to be true on the payoff matrix of a two person game for it to be an example of the prisoner's dilemma?

Nash equilibrium

Define "Nash Equilibrium" and give an example

Newcomb's Paradox

You and a friend are presented with two boxes. The first box is transparent and contains $1,000. The other box is opaque and either contains nothing or $1 million. A mysterious benefactor offers you this choice and tells you that you may choose to take both boxes or just the opaque box. "However," your generous benefactor cautions, "If I expected you to take both boxes, I have left the opaque box empty -- you get only the $1,000." The mysterious person continues. "If I predicted that you would take only the opaque box, then I have placed $1 million in that box. You will get it all." You and your friend begin to discuss what to do. Your friend wants to take just the opaque box. You argue that the benefactor has already made his prediction -- the million dollars is either in the opaque box or it is not. It is not going to change. Use the tools of game theory to and decide whose argument is more correct.

Knowledge representation


Situation calculus

The Prince of Pizza has a magic wand that will turn a frog into a pizza. However, it only works if he is holding the wand, the wand is touching the frog, and he says "Presto." Write a situation calculus description of the Presto action. Use an effect axiom and a frame axiom. Do not use a successor-state axiom.

Representing Actions

Consider representing the action of toggling a light switch. That is, if the light is on, toggling the switch will cause the light to be off, and if the light is off, toggling the switch will cause the light to be on. Using the predicates LightSwitch/1, On/1 and Off/1 , answer the following:
  1. Write one or more effect axioms in the Situation Calculus that define the action "toggle." Use just one action called Toggle if possible; if not, use more and explain why more are needed.
  2. Write a frame axiom that says any object x at any location y remains at that location after toggling any light switch. Use the predicate location/2 in your answer.
  3. Write one or more STRIPS-type operators that represent the action "toggle." Use just one operator called Toggle if possible; if not, use more and explain why more are needed.

Wolf, goat, and cabbage

A man has to take a wolf, a goat, and some cabbage from Moscow to Petersburg across a river. His rowboat has enough room for the man plus either the wolf or the goat or the cabbage. If he takes the cabbage with him, the wolf will eat the goat. If he takes the wolf, the goat will eat the cabbage. Only when the man is present are the goat and the cabbage safe from their enemies. Initially, the man, cabbage, goat, and wolf are on the Moscow side of the river. All the same, the man carries wolf, goat, and cabbage across the river.

  1. Design a domain description for this problem using the STRIPS representation as discussed in lectures and the homework. You can use variables in the preconditions and effects of operators.
    • Write down the objects used by your domain description
    • Write down the predicates used by your domain description
    • Write down the operator definition (name, preconditions, add list, and del list, conditions) used by your domain description
  2. Write down the expression for the initial state
  3. Write down the goal expression for the problem above

Partial order planning

Progression and regression

Whats the difference between a progressive planner and a regressive planner? Hint: this has nothing to do with politics.


Jess one

Assume we have unordered Jess facts like the following to represent a person's various income sources:

     (income joeSmith salary 50000)
     (income joeSmith consulting 5000)
     (income joeSmith interest 50)
     (income joeSmith investments -1000)
Write one or more Jess rules which will determine each individual's total income, asserting a fact like the following into the database:
     (totalincome joesmith 54050)

Jess two

Write a set of Jess expressions (e.g., defrules and deffacts) to model the following sentences. What additional facts would your sentences assert.

     all birds have wings.
     Assume a bird can fly unless you know it can't.
     sparrows are bird.
     penguins are birds.
     Hoppy is a sparrow.
     Tux is a penguin.
     Penguins can not fly.

Jess three

Describe what will happen when the following file is loaded into Jess.
...to be supplied...


Decision Trees

We would like to predict the gender of a person based on two binary attributes: leg-cover (pants or skirts) and beard (beard or bare-faced). We assume we have a data set of 20000 individuals, 10000 of which are male and 10000 of which are female. 75% of the 10000 males are barefaced. Skirts are present on 50% of the females. All females are barefaced and no male wears a skirt.
  1. Compute the information gain of using the attribute leg-cover for predicting gender!
  2. What is the information gain of using the attribute beard to predict gender?
  3. Based on yours answers to (1) and (2) which attribute should be used as the root of a decision tree?
  4. What is the "intuitive idea" that underlies ID3's information gain heuristic --- what attributes does it prefer?
  5. How can the information gain heuristic that was originally designed for symbolic attributes be generalized to cope with continuous attributes?


Define the overfitting problem in inductive learning. Why is it a problem. Give a simple example to illustrate overfitting. What are some techniques that can help solve the overfitting problem?

Decision trees

You've been hired as the IT person for the newest trendy bar in Canton. Your boss wants to predict how much business they will do so he can ensure she has enough staff and food for the day. She hasn't gathered much data yet, but she still wants you to build a decision model.



(a) Which attribute would be the first one selected when using the ID3 algorithm?

(b) Calculate the information gain for each of the three attributes (DOW, Rainy, Temperature). You need not simplify the formulae.

(c) Construct a decision tree using the ID3 algorithm.

(d) Tomorrow is Wednesday and the outlook is that it will be hot and rainy. What do you tell your boss about how many customers to expect?

(e) The weather prediction for Saturday is that it will be sunny with either a hot or moderate temperature. Your boss is anxious to plan for the weekend and wants your system to work even when the weather predications are uncertain. How could you modify a decision tree to make reasonable predictions even when all of the attributes are not known?

Evaluating learning systems

Explain briefly (2 or 3 sentences) the use of a training set and a test set in evaluating learning programs.

Supervised and Unsupervised learning

Explain the difference between supervised and unsupervised learning.

Ockham’s razor

Ockham’s razor favors some generalizations over others. What is Ockham’s razor and how can it be operationalized? Use decision tree induction as an example to illustrate.

Decision trees

Given the following decision tree. How would ID3 classify the following new pieces of data?
                   Blue|     Red|   Green|
                       |        |        |
                     Width      No    Height
                  -----------        ---------
              Thin|      Fat|   Short|    Tall|
                  |         |        |        |
                  No       Yes       No      Yes

        New Data:
        Example Color Height Width
        A       Red   Short  Thin
        B       Blue  Tall   Fat
        C       Green Short  Fat
        D       Green Tall   Thin
        E       Blue  Short  Thin

Self organizing systems