Review Questions
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.

Past Exam Questions


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


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

Past Exam Questions

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

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


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:

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.

Past Exam Questions

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?

Past Exam Questions