Question 1: Search

a) Explain why breadth-ﬁrst and iterative deepening search do not always ﬁnd the

optimal solution. Under what circumstances is the solution they ﬁnd optimal? Be

as precise as you can.

[20]

b) Explain how you would modify each search to ensure that they always ﬁnd the

optimal solution. Prove this for both types of search, using a proof by contradiction.

[30]

c) Implement and experimentally compare the performance (in terms of both the

number of nodes expanded during the search – representing the time complexity

– and the maximum number of open nodes stored in memory – representing the

space complexity) of the standard versions of breadth-ﬁrst and iterative deepening

searches.

Evaluate your implementations using the Missionaries and Cannibals search problem given in Russell and Norvig.

[20]

Your program should be written in well-commented Java, and you should include

explicit instructions on how to compile, run and execute it.

Submit the following:

1. Written answers to parts a) and b).

2. A written report describing the performance of each algorithm and summarizing the results, for part c).

3. A well commented digital copy of your program source code and executable

for part c). Include a ﬁle named README.TXT that explains how to run the

program, and include a copy of any additional software or libraries required.

Question 2: Knowledge Representation and Reasoning

PROLOG is a declarative programming language that allows you to create a knowledge base by writing ﬁrst-order logic sentences, and then pose queries to that

knowledge base. The language itself takes care of performing the necessary inference; your role is primarily that of correctly specifying the problem and the

query you need answered.