Due: Thursday, October 29, 2009 at the beginning of class

• Follow the general directions for homeworks.
• Answer the following questions:

1. (10 points) Question 3.7 in AIMA.

2. (10 points) Question 4.9 in AIMA.

3. (30 points) Implement the RBFS algorithm. This must be written from scratch by you. You may use the pseudo code in the book as a guide, but you may not use others code. Apply RBFS to the 8/15/24/n^2-1 puzzle.
   • What is the largest puzzle that you can solve on a 2GHz Pentium with 1GB of memory in one hour (~8 x 10^12 machine cycles) with RBFS? If you don't, which of course you don't, have exactly this machine configuration, scale your processor to this size. Yes, I know this is not an ideal measure of a machine, but it is an easy, almost reasonable one.
   • For each of the smaller puzzle sizes, time how long it takes to solve 30 random initial puzzle layouts. What is the average and standard deviation amount of time it takes to solve?

   • Make sure that the puzzles you attempt to solve are solvable. Either check the puzzle or create it in such a way that guarantees that the puzzle is solvable.

4. (30 points) Solve the same problem (same computation limits) with at least two other search algorithms. In this case you may use code written by others, make sure to document where you got the code. The solutions will be rank graded according to their performance. Compare the search algorithms you investigated.