CSE2309/3309 Artificial Intelligence 2000

Note: The following problems are by no means exhaustive of the scope and range of what is examinable in the subject. They are intended only to give some idea of the variety and type of questions you may find on the exam. Assessable material is all of the contents of the lectures and readings in the subject. Second Note: Answers will be made available by consultation only.

Exercise Set 1: LISP

Exercise 1.1

Describe what the following function does. 
(defun mystery (x y)
  (and (consp y)
       (let ((p (car y)))
         (if (eql x (car p))
	     p
	     (mystery x (cdr y))))))

Exercise 1.2

  1. What is the difference between do and do*?
  2. What does the following instruction do: 
    (mapcar #'(lambda (x) (/ 1.0 x)) '(4 3 2))

Exercise 1.3

Define a function palindromize which takes a list and returns a palindrome twice as long. (NB: A palindrome is a list that has the same sequence of elements read left to right as right to left.)

For example, 

(palindromize '(a (b c d) e))
would generate the return value (a (b c d) e e (b c d) a).

Exercise Set 2: Logic

Exercise 2.1

Explain the frame problem for logical systems in AI.

Exercise 2.2

Do exercise 7.2 in Russell and Norvig (p. 213).

Exercise 2.3

Describe Gödel's incompleteness theorem for arithmetic. What are its implications for AI, if any? Defend your answer.

Exercise Set 3: Search

Exercise 3.1

Invent a heuristic function for the 8-puzzle that sometimes over-estimates and illustrate how it can lead to a suboptimal solution.

Exercise 3.2

What is the time complexity of the following algorithms:
  1. Breadth-first search.
  2. Depth-first search.
  3. Uniform-cost search.
  4. A* search.
  1. Describe uniform-cost search.
  2. Describe A* search.
  3. What is the relation between the two?

Exercise 3.3

Describe alpha-beta pruning in game search. How does it differ from the minimax algorithm without pruning?

Exercise Set 4: Planning

Exercise 4.1

Present the POP algorithm in pseudo-code.

Exercise 4.2 (from R & N, 11.9)

There is a monkey in a room with some bananas hanging out of reach from the ceiling. There is a box available which would enable the monkey to reach the bananas if he were to climb on it. Initially, the monkey as at A, the bananas at B and the box at C. The actions available to the monkey are: Go from one place to another; Grasp an object; Climb an object; Push an object from one place to another.
  1. Write down the initial state description in predicate calculus.
  2. What is the monkey's goal?
  3. Write down STRIPS definitions of the four actions, providing both preconditions and effects.
  4. Use the POP algorithm to generate a plan for the monkey.

Exercise Set 5: Learning

Exercise 5.1

  1. Describe the main features of a feed-forward artificial neural network.
  2. How do they differ from the perceptrons criticized by Minsky and Papert in 1969?

Exercise 5.2

  1. What are two of the main genetic operators applied to chromosomes in reproduction in Genetic Algorithms?
  2. Define fitness in evolution theory. Define fitness for Genetic Algorithms. What is the relation between the two?
  3. Give the algorithm (in pseudo-code) of Genetic Algorithms.

Exercise 5.3

Consider the problem of playing GOMOKU. GOMOKU is five-in-a-row played on a 19x19 board -- i.e., it is like TIC-TAC-TOE (noughts-and-crosses) but played on a larger board and requiring five in a row be achieved rather than three. Define a genetic algorithm that can learn to play decent GOMOKU:
  1. Design a chromosome structure that makes sense.
  2. Describe useful crossover and mutation operators for the chromosome.
  3. Define a fitness function.

Exercise Set 6: Probabilities & Utilities

Exercise 6.1

You are an MEU (one who maximizes expected utility). Suppose you believe the probability that lottery 1 will win (L1) is 0.4 and the probability that lottery 2 will win (L2) is 0.6. Suppose also that you have a choice between lotteries 1 and 2 (you can have one or the other but not both) and that they are free. You choose L1. What can an external observer say about your utility function?

Exercise 6.2

Suppose that a patient turns up with a cough. This cough can either be a symptom of bronchitis or l ung cancer. Factors which the doctor may take into account include the results of an x-ray (if it is cance r, the x-ray will be positive 95% of the time, and if there is no cancer the x-ray will always be negative ), and whether or not the patient is a smoker or not (twice as many smokers as non-smoker will have cancer ). Model this diagnosis problem in a Belief network with Boolean variables for smoker, cancer, Xray, bronchitis, and cough.
Disclaimer