TEST 1 CS724

Instructor Dr P Juell    NAID______________________ NAME__________________________
100 points, closed book                                  Feb. 6, 2001

1. (20) For the following tree, Goal states have an -G after the node number. If you need edge costs, they are given. Specify which, if any goal will be found by each search technique. (The node numbers are 1, 2, 3, 4-G, 5, 6-G, 7-G, 8, 9, 10-G).

   Depth first ____________

   Breadth first __________

   Branch and Bound _______

   

2. (20) Give two major ways an esimate of answer quality (game outcome) be used to reduce search space in large game trees. Describe the way it is used, not just the name of the technique.

   Do the above techniques effect the answer quality? Explain.

3. (20) For the blocks world, you are to change the program so you can not place an object on another object, if they are both the same color. Where in the program would you make this change, and what would your code do?

   Someone suggested that you do this in the move function. What problem would this create, and how can this be solved?

4. (20) The following is an AND/OR tree, but none of the arcs are shown. A minimal set of leaves that could be visited is (b, d, e, f, g, l, o, r, s, t). Draw in the arcs to make this work.

   

5. (20) Write a lisp program to produce the logical difference of two lists. For example if the input was
   (setdif '(a b c d e) '(d a)) the output would be (b c e). You can write as many functions as you want/need. Also (equal 'a 'b) will return t if the two are the same. To do this, you will probably want to write a function called member that checks if an item is in a list. (For reduced credit, you can assume that both lists are in alphabetical order with no repleats in the lists).