.nh
.po 5
.ce
TEST I CS524
.nf
Instructor Dr P Juell                           NAME__________________________
100 points, open book                                      Jan 11, 1990
.fi

1. (20)
Write the LISP code to produce the following effect.  The routine THIRD
will list out every third item in a list.  For example:
.nf
.in +5
FUNCTION CALL                                OUTPUT
(THIRD '(a b c d e))                         (c)
(THIRD '(a b c d e f g (h i) (j k)))         (c f (j k))
.fi
.in -5

2. (20)
Place an X in boxes where the description is appropriate for the stated search.
.nf
                   depth    breadth	 branch &   hill      best
	           first    first        bound      climbing  first
requires        |         |          |            |          |       |
metric          |         |          |            |          |       |
                ------------------------------------------------------
backtracks      |         |          |            |          |       |
                |         |          |            |          |       |
                ------------------------------------------------------

is admisissible |         |          |            |          |       |
                |         |          |            |          |       |
                ------------------------------------------------------

minimal storage |         |          |            |          |       |
requirement     |         |          |            |          |       |
                ------------------------------------------------------

.fi

3. (20)
Give an example tree that will not have all its nodes inspected in
an alpha-beta search.  
The tree is to have three branches at the root and
two at each node on the second level.

4. (20)
Write the PROLOG program for the following information and the query
to determine if John is older than Mary.
John is older than Mark.  Mark is younger than Jane.
Mary is younger than Mark.
Jane is younger than Carol.

5. (20)
The blocks world blocks are to be permitted to store water.  When a block is
set on top of another block (say A on B),  
if there is space left, the water will flow
into the supporting blocks.
That is water will flow from block A to B (and possibly to the block supporting
B).
What changes will be required to the existing blocks program to implement this?
(There is an important routine that you need to give the pseudo code for).