Homework 1: Turing test and search

Out: Tuesday, 9/19/06

Due: Wednesday, 9/27/06


This assignment consists of written exercises only (the next assignment will also involve programming).  See the assignments page for information on when and where to submit written exercises.

Note: if you have not yet received the textbook, please refer to questions 3.7 and 3.13 here (questions will be removed from the web on September 26).

Remember that if you do not already know Java, you should be learning it at this time (for instance, by reading Java in a Nutshell).

1.  There are many "chatterbots" on the web that attempt to carry on human-level conversations, often within a limited domain.  These include:

Have a "conversation" with one or more of these chatterbots.  Try to test what they can or cannot do, what they are good at, and what they are not so good at.  See what you can learn about how they work.  Then briefly (say, in three paragraphs or less) describe and analyze your experience.

2.  Problem 3.7 in R&N (where successor function refers simply to the actions that are possible from each state).

3.  Consider the following search problem:

The states are: A, B, C, D, E and F.  The initial state is A.  The goal state is E.  The actions permit movement along directed edges (for instance, from B, we can move to C, D or E).  Assume unit step cost.

Draw the search tree that would be produced by running each of the search algorithms BFS, DFS and IDS on this problem.  When multiple nodes are added all at once to the fringe (or queue), assume they are added in such a way as to be removed later from the fringe in alphabetical order.  If a goal state is reached, indicate the solution (sequence of states) that was found and whether or not it is optimal.

For IDS, give separate answers for each choice of the depth parameter.

4.  Problem 3.13 in R&N.  Be sure to justify your answer.