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.
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.
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
Evaluate your implementations using the Missionaries and Cannibals search problem given in Russell and Norvig.
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.