COSC 387: Artificial Intelligence
Project 1
Fall 2002
Due: Oct 1 @ 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 print the pre-order and post-order traversals of the tree
passed in as the argument, respectively.
- 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 (2 points)
- 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 Submission:
In the header comments, provide the following information:
;;;;
;;;; Name
;;;; E-mail Address
;;;; Platform: Windows, Linux, Solaris (cssun)
;;;; Lisp Environment: gcl, clisp, cmucl
;;;; Mail Client: mailx, pine, GUMail, Netscape, Yahoo!, etc.
;;;;
When you are ready to submit your program for grading, e-mail it to
Mr. Headden
as one file with your net ID and the suffix ``.lisp'' as the subject line.
For example, if you were to submit using mailx on cssun, and if your net ID
is ab123 and the name of your source file is proj1.lisp, then type at the
UNIX prompt:
cssun% mailx -s "ab123.lisp" headdenw < proj1.lisp
If you use some other mail client, then follow the same instructions, and
send your code as an attachment.
Submit your project before 5:00 P.M. on the due date.
Once submitted, it is important to keep an electronic copy of your
project on either cssun or gusun. If we lose your project
or the e-mail 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. If you developed your code on a Windows machine, then use a secure
ftp client to transfer your file to cssun or gusun.
Finally, when storing source code on university machines, it is
important to set file permissions so others cannot read the file.
To turn off such read/write permissions, type at the UNIX prompt
chmod og-rw <file>, where <file>
is the name of your source file.