CSci 4511 - Homework 1

Homework 1 -- due Tuesday February 2

This homework will be graded out of 100 points. It will count 6% of the grade.

Written questions

This part has to be turned in on paper.

[10 points] Question 3.6 (page 90) of the 2nd edition of the textbook. The question is not in the 3rd edition. Here it is: "Does a finite state space always lead to a finite search tree? how about a finite state space that is a tree? Can you be more precise about what types of state spaces always lead to finite search trees?"
[20 points] Question 3.7 of the 2nd edition of the textbook. The equivalent question from the 3rd edition is 3.6.
[20 points] Question 3.9 of 2nd edition of the textbook. The equivalent question from the 3rd edition is 3.9. You do not need to implement the missionaries and cannibals since you'll use the AIMA implementation for the LISP part.
[15 points] Question 3.15, parts a and b of the 2nd edition of the the textbook. The equivalent question from the 3rd edition is 3.7.
[15 points] Question 3.17, parts a, b, and c of the 2nd edition of the textbook. The equivalent question from the 3rd edition is 3.8.

Lisp questions

This part has to be turned in electronically using the Submit Tool. You need to submit the output of your programs when you run Lisp. Look at Capturing Lisp Output for how to do it. The first method, using the Lisp function "dribble" is the easiest, but if you use Unix you can also use the unix "script" command.

[10 points] Download and install the Lisp code from the AIMA book. We will use the search and agents part. Here are the steps:
- make sure you have a Lisp system working. Look at Lisp Info for information on the implementations available in the itlabs and for free implementations you can download.
- Go to http://aima.cs.berkeley.edu/lisp/doc/install.html and download the code. Follow the instructions to install the code, specifically step 1 which requires to edit the file "aima.lisp" to change the value of the parameter *aima-root*. If you want to save time, you can shorten step 4 by doing the following:
```
(load "aima.lisp")
(aima-load 'agents)    ; loads the agents subsystem
(aima-load 'search)    ; loads the search subsystem
(aima-compile 'agents) ; compiles the agents subsystem
(aima-compile 'search) ; compiles the search subsystem
(test 'search)         ; tests the functions in the search subsystem
(test 'agents)         ; tests the functions in the search subsystem
```
  When I did this part, using CLISP, I got an error message in the file agents/environments/wumpus.lisp, since kill is a system defined macro and should not be redefined. I fixed the problem by changing all occurrences of kill to something else. I also got a warning about redefining agent-body, but the program compiled fine.
- Test the search subsystem by typing:
```
(test 'search)         ; tests the functions in the search subsystem
```
  Check that there are no errors (look at the last line printed).
[10 points] The missionaries and cannibals problem is defined in the "search/domains" part of the code. For documentation on the functions defined in the aima search system, look at http://aima.cs.berkeley.edu/lisp/doc/overview-SEARCH.html It lets you drill down to the lisp code in all the directories and subdirectories. You do not need to use deftest for your programs. If you decide to use deftest you can find its documentation in http://aima.cs.berkeley.edu/lisp/doc/overview-UTILITIES.html under Testing Tool: deftest and test. deftest is a macro, so it follows different evaluation rules.
1. Run the missionaries and cannibals with 3 missionaries and 3 cannibals with one of the available search algorithms. Look at the file "search/test-search.lisp" for eaxmples on how to call the functions to create a missionaries and cannibals problem and to solve it with a search algorithm.
  I recommend not using deftest for your programs, but calling your functions directly. For instance, to create a problem with 2 missionaries and 1 cannibal you need something like:
```
(setq p1 (make-cannibal-problem
	     :initial-state (make-cannibal-state :m1 2 :c1 1)))
```
2. Change the number of missionaries and/or cannibals until you find a problem that has no solution.

To understand the Lisp code from the AIMA book, you need to read Chapter 3 from Lamkins ("Structures let you store related data" i.e. (defstruct) and Chapter 6 (use of keywords and default values in structures). You also need to understand the notation #'.