COSC 387 Project 1

COSC 387: Artificial Intelligence

Project 1
Spring 2008

Due: Feb 7 @ 5 P.M.
4 points

Write a function that uses the do form to find the minimum and maximum values in a list of numbers. The function should return these two values in a list. Do not use the min and max functions in your implementation.
Same problem as above, but use recursion.
Same problem as above, but use apply, min, and max.
Encode the following tree as a list assigned to a globally declared variable. Write two Lisp functions, preorder and postorder, that returns as a list the pre-order and post-order traversals of the tree passed in as the argument, respectively.

For example,
```
> (preorder *tree*)
(O R E G O ... )
```
Encode the following graph using property lists. Write a Lisp function that, when given a start and an end node, uses depth-first search to return a path between them.

For example,
```
>(dfs 'a 'g)
(A C F E G)

>(dfs 'f 'g)
(F E G)

>(dfs 'e 'c)
NIL
```
Develop a representation for a tic-tac-toe board. Write a function that, when given a board configuration as its argument, returns a list containing all of the next possible moves.
Tanimoto defined a heuristic evaluation function for tic-tac-toe boards as
f = 100A + 10B + C - (100D + 10E + F),
where
- A is the number of lines with 3 X's,
- B is the number of unblocked lines w/ 2 X's,
- C is the number of unblocked lines with 1 X,
- D is the number of lines with 3 O's,
- E is the number of unblocked lines w/ 2 O's, and
- F is the number of unblocked lines w/ 1 O.
Implement Tanimoto's heuristic evaluation function. That is, when given a tic-tac-toe board configuration, the function returns f.

Extra Credit (1 point each)

Conduct a timing study using your three implementations of the “min-max” function (items 1–3 above). Write a function that returns a list of 1000 random numbers. Write another function that generates 1000 such lists, giving each to the three implementations of the min-max function. Use the time function to determine how much time each implementation requires to process the 1000 lists. Which is faster? Why?
There are two possible ways to iterate through a list. One can use dolist or one can use dotimes, length, and nth. Using the functions above, iterate through 1000 lists of 1000 random numbers using both of these methods and time them. Which is faster? Why?

Instructions for Electronic Submission

In the header comments of the primary file, provide the following information:

;;;;
;;;; Name
;;;; E-mail Address
;;;; Platform: Windows, Linux (seva), etc.
;;;; Lisp Environment: clisp, gcl, cmucl
;;;;
;;;; In accordance with the class policies and Georgetown's Honor Code,
;;;; I certify that, with the exceptions of the course materials and those
;;;; items noted below, I have neither given nor received any assistance
;;;; on this project.
;;;;

You'll be using the submit program to submit your assignments. To get the submit program, on seva, type

seva% cp /home/maloofm/cosc387/submit.jar ./

Copies of the submit program from previous semesters will not work, so get a fresh copy.

If you need to submit a single file, assuming its name is p1.lisp, type

seva% java -jar submit.jar -a p1 -f p1.lisp

If you need to submit multiple files, if you haven't already, place all of your code in a subdirectory named p1. To create this subdirectory, type

seva% mkdir p1

To descend into the directory, type

seva% cd p1

All of the files for your project should be in this directory. The submit program should be above this directory:

seva% ls ..
p1/ submit.jar

If you need to include a message to me about your submission, then place the message in a file named README. Place the README file in the project's directory.

To move up from the p1 directory, type

seva% cd ..

You should be above the p1 directory:

seva% ls
p1/ submit.jar

(Additional useful Unix commands)

When you're ready to submit, change the name of the directory to your netid. For example, if your netid is maloofm, then rename the directory p1 by typing

seva% mv p1 maloofm

Create a zip file of the directory and its contents by typing

seva% zip -r p1.zip maloofm/*

This command creates a zip file named p1.zip by recursively (-r) copying all of the files (*) from the directory maloofm/.

To submit the zip file type

seva% java -jar submit.jar -a p1 -f p1.zip

p1 is the name of the assignment (-a) and p1.zip is the file (-f) to be submitted for that assignment.

If the program submits the file successfully, you will receive a receipt by e-mail at the address <netid>@georgetown.edu.

Submit your project only once.

Once you've submitted your project, it is important to keep an electronic copy on a university machine (e.g., seva) that preserves the modification date and time. If we lose your project or the submission system breaks, then we will need to look at the modification date and time of your project to ensure that you submitted it before it was due.

You can also change the directory's name back to the original name. For example,

seva% mv maloofm p1

Note that changing the name of the directory does not change the dates of the files in the directory. You can also remove the zip file from your directory:

seva% rm p1.zip

You must submit your project before 5 PM on the due date.

Plan B

If something goes wrong with submit, then send your project as an attachment to an e-mail to me.