Project 1

Fall 2010

Due: Wed, Sep 29 @ 10 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?

;;;; ;;;; 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 Blackboard to submit your assignments. Put everything in a zip file and upload it.

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

*
Copyright © 2019 Mark Maloof. All Rights Reserved.
This material may not be published, broadcast, rewritten,
or redistributed.
*