Written Exercises W1
|
Fall 2012
|
Numbers in brackets indicate approximate number of points each problem is worth. See the course home page for information on when and where to submit written exercises, and grading criteria.
1. [10] 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. [15] Exercise 3.15 in R&N.
3. [10] Exercise 3.18 in R&N. Be sure to justify your answer.
4. [15] Consider the following toy search problem:
The states are the vertices of this graph. The start state is S, and the goal state is G. The actions permit movement along directed edges with costs as indicated. (For instance, the cost of moving from S to U is 2; the cost from U to V is 9.) The numbers in blue by each vertex indicate heuristic h values. (For instance, h(S)=9; h(U)=10.)
a. Show that this choice of h is consistent.
b. Draw the search tree that would result from running greedy best-first search. Also number the nodes of the search tree in the order in which they are expanded. For instance, place the number 1 by the start node (associated with the start state S).
c. Do the same thing for A*. Also indicate the g and f values associated with each search node.
5. [10] Exercise 3.29 in R&N. Also, answer the following: Does the admissible-but-not-consistent heuristic that you constructed have the monotone property that we discussed? In other words, is it the case that the f-values are nondecreasing along every path?