last updated 20/04/04

Introduction: History and Philosophy

0. 1. What are the philosophical issues raised by the Chinese Room Argument and the Brain Prosthesis Experiment ?

0. 2. Briefly discuss four different motivations for implementing AI systems, thinking and acting rationally, thinking and acting like humans.

0. 3. Who coined the term “Artificial Intelligence” and when?

0. 4. Describe the Turing test for determining if an AI system has succeeded.

Agents:-

1. 1. What is the difference between a performance measure and a utility function?

1. 2. In terms of an agent, what does it mean to say that its environment is accessible? inaccessible?

1.3. What are the four different types of agent systems ? Briefly describe each.1.4. What type of agent is a table lookup agent ? What are the problems with a table lookup agent ?

1. 5. We usually consider the following aspects of an agent:
Percepts,
Actions, Goals, and the Environment. Environments are categorised
according to the following aspects: Accessible - inaccessible,
deterministic
-nondeterministic, episodic - nonepsiodic, static - dynamic, discrete -
continuous.

Discuss what kind of environment we have and what kind of agent should
be used for the following tasks:

a. Vacuum cleaning your house,

b. Making recommendations for the stock market,

c. A helpdesk agent for the School's computing facilities.

Past Exam Questions

Search

2.1. What is a successor function?

2.2. When we say a particular search strategy is complete, what do we mean?

2.3. What is the time complexity of breadth-first search?

2.4. What is the space complexity of breadth-first search?

2.5. What is a main drawback in using breadth-first search in real-world problems?

2.6. What is the time complexity of depth-first search?

2.7. What is the space complexity of depth-first search?

2.8. What is a main drawback in using depth-first search in real-world problems?

2.9. Explain why the problem formulation must follow the goal formulation.

2.10. Describe a search space in which iterative deepening search performs much worse than depth-first search.

2.11. Describe a search space in which breath-first search performs
worse than depth-first search

and another search space where depth-first search performs worse than
breath-first search.

2.12. Consider the tree below:

List

i) nodes expanded and

ii) solution found

when each of the following search strategies is used:

a) BFS.

b) DFS

c) UCS

d) Iterative deepening

2. 13. Given a search tree of depth two and branching factor of two,
what is the worst case time and space complexity for depth first and
breadth
first search ? Show your working.

Informed Search

3.1 Suppose that we run a greedy search algorithm with h(n)=-g(n). What sort of search will this search emulate?

3.2 What is an admissible heuristic ?

3.3 Describe the A* algorithm?

3.4 Given that h is an admissible heuristic, prove that the A* algorithm is optimal.

3.5 Normally we think of the A* algorithm being complete. Under what
conditions would A* not be complete?

3.6 Consider the following heuristics A and B for the 8-puzzle:

A: The number of tiles which are not on their target location.

B: The sum of the Manhattan distance of each tile beween its current
location and its target location.

Does A) A dominate B? B) B dominate A? C) Neither nor? D) both, A
dominate
B and B dominate

A?

3.7 Briefly describe the iterative hill climbing strategies for finding solutions in a search space. What are the time and space complexity of this algorithm ?

3.8 Briefly describe what simulated annealing is. What are the
time and space complexity of this algorithm ?

Past Exam Questions

Logic

4.1 What does it mean that an inference procedure is sound?

4.2 Is the following sentence valid, satisfiable or unsatisfiable
((P
OR H) AND P) <=> ((P AND H) OR P)?

Use a truth table or inference rules, not intuition. Show your work.

4.3 Using the inference rules, show that S can be inferred if the
following
five sentences are

believed. Briefly explain your deductive steps.

1. P

2. P => R

3. P => NOT W

4. S OR R

5. P AND R => S OR W

4.4 Use resolution to show that P is a logical consequence of the
set:

{ Q OR P, NOT Q OR R, NOT R OR S, NOT S OR NOT R OR T, NOT T OR P }

4.5 Use the definition of logical consequence and a truth table to
show
that

(Q => P) OR NOT(Q => (P OR R))

is a logical consequence of the set:

{P OR Q OR R, R => (P OR Q), (Q AND R) => P, NOT P OR Q OR R }

4.6 Consider a world with 3 blocks : a red one, a black one, and a
white
one. A tower is built using these 3 blocks. A red block and a white
block
can't be placed on top of one another. Show that the block at the
bottom
of the tower can not be black by writing out a description of the state
in which the bottom block is black and using the rules of inference to
prove that it is an invalid state.

You can use the following representation scheme:

XY means "X is on top of Y", where X and Y are two distinct blocks,

e.g. RB means "Red is on top of Black".

XT means "X is on the table", where X is a block, e.g.BT means "Black
is on the table."

Indicate what rules of inference you used when writing the proof.

Past Exam Questions

Fuzzy Logic

5.1 Describe the main differences between classical set theory and fuzzy set theory. Compare the classical and fuzzy set operators.

5.2 Define the term set membership function, illustrating your answer with an example. Sketch the graph of your fuzzy membership function example.

5.3 Discuss how fuzzy logic is an extension of classical logic, define the fuzzy logic operators and give their definition.

5.4 Identify the role of fuzzification, fuzzy rule inference and defuzzification in a fuzzy control system

5.5 Design a fuzzy controller for a refridgerator given the following technical specifications.

The ideal temperature of the fridge is 2 degrees centigrade, while the variation in internal temperature is not expected to be more than +5 or -5 degrees. The maximum rate of change of temperature is expected to be within +2 or -2 degrees per hour. The output from your fuzzy controller is expected to power a compressor that ranges from 0 to 2 kW.

Given a temperature of 4 degrees and a rate of change of temperature
of -0.5 degrees per hour, what is the required compressor power output
calculated by your controller.

Game Playing

6.1 Why does the effectiveness of alpha-beta pruning depend on the order in which branches are developed?

6.2 The minimax algorithm returns the best move for MAX under the assumption that MIN plays optimally. What happens when MIN plays suboptimally?

6.3 Consider the following search tree from a two-player zero sum
game.

What is the correct value for the root node A according to Minimax?

6.4 Given the fact that expansion takes place from left to right:
how
many leave nodes would alpha-beta search

evaluate in the game tree from the previous question?

6.5 What is the value alpha-beta pruning assigns to the root node?

6.6 If successors are ordered optimally (the best successors
are
examined first), with a tree with branching factor b, what is the
effective
branching factor with minmax search with alpha-beta cutoffs? What does
that mean in terms of the depth one can search with alpha-beta cutoffs
contrasted with minmax alone?