COSC 187/387: Artificial Intelligence

Project 1
Fall 2004

Due: Sep 27 @ 5 P.M.
4 points

  1. Write a function that uses the do form (not dolist and not dotimes) 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.

  2. Same problem as above, but use recursion.

  3. Same problem as above, but use apply, min, and max.

  4. 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?

  5. 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.

  6. 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
  7. 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.

Instructions for Submission

Submit your project as a single file. In the header comments, provide the following information: 
;;;;
;;;; COSC [187|387] Project 1
;;;; Name
;;;; E-mail Address
;;;; Platform: Windows, Linux, Solaris (gusun, daruma)
;;;; Lisp Environment: gcl, clisp, cmucl
;;;;
Place the results of the timing study in the header comments.

Submit your project as a single file as an attachment to an e-mail. Send the e-mail to me. The attachment should be named so that the file stem is your NetID and the extension is .lisp.

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

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.