CSE logo University of Washington Computer Science & Engineering
 CSE 473: Artificial Intelligence I
  CSE Home   About Us    Search    Contact Info 

Administration
 Course Index
 Syllabus
 Email Archive
 Schedule as RSS
   

Problem Set #1

Guidelines

  • Reading: Chapter 1 and 3 (you can skip Chapter 2).
  • Due: Oct. 8th at the beginning of class.
  • Problem sets have to be typed, hard copy, and legible.

Problems

  1. Problem 1.7 in the textbook. Please just answer yes or no. Your "yes" could contain a one sentence caveat or qualifier. You need not do the part that starts with "For currently..." at the bottom of the question.
  2. Problem 3.9. Please turn in your well-documented code and a trace.
  3. Problem 3.13. Be precise and succinct.
  4. Problem 3.14. You don't need to write a program, just answer the questions clearly and succinctly.

A note on Problem 3.9

In order to make your lives and my life easier, I'd like to narrow down what I'm looking for in terms of the program execution trace. As your program searches through states, I'd like to see a line of output as STATE + NEXT ACTION. Let's see an example:

33 00 L    One missionary and one cannibal move to the right
22 11 R    One missionary moves to the left
32 01 L    Two missionaries move to the right
12 21 R    Cannibals feast on the left bank
33 00 L    One cannibal moves right
32 01 R    ...

At each step, we have a five digit state tag indicating the following:

<# missionaries on the left bank><# cannibals on the left bank> <# missionaries on the right bank><# cannibals on the right bank> <where is the boat? (L/R)>

We additionally have a text string describing what the next action to be performed is. As you can see from the example, all three missionaires and all three cannibals start with the boat on the left bank (33 00 L). Our next action is to move a missionary and cannibal to the right bank, giving us the next state of (22 11 R). Tracing continues until we end up with more cannibals than missionaries being left behind on the left bank (12 21 R). At this point, you can start searching from somewhere else, as in our jump back to (33 00 L), the start state, in this example.

Since program trace will likely contain lots of dead ends before finding the working solution, I'd also like to see a final list of steps for a solution to the cannibal / missionary problem. So all told, I'll be looking for documented source and two sets of trace (the program run and a solution).

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to bdferris]