CSE 151 Programming Assignment 2

---

Introduction to Artificial Intelligence

---

Due Thursday, May 16, at the start of class.

The GSAT algorithm

The details of the assignment are given in problem 6.15 on pages 182-4 of the book. Please read it carefully and do all parts.

What To Hand In

You may work alone or in groups of up to three people on the programming assignments (including this one).

Turn in the code using the turnin utility by the date and time given above. This is done by placing all of your Lisp code into a single source code file called, say, "gsat.lisp", and then executing:

% turnin -c cs151s gsat.lisp

The turnin program will print out some messages, including the size of the file submitted. Make sure that this size is reasonable (and that you haven't turned in something else by mistake). Make sure that the names and login IDs of all group members appear clearly in a comment at the top of your source file.

When working as part of a group, only one group member needs to submit the group's source code using turnin. Just make absolutely sure that all group members have their names and login IDs in a header comment in that file.

Each group should also bring to class and hand in a full listing of the code. In addition, each member of the group must turn in their own written document. This document should

• Explain how the program works.
• Answer the questions posed in parts a, b, c, d, e and f of question 6.15.

Make sure you clearly identify all the members of your group on everything you hand in.

Further Coding Specifications

• The name of your main GSAT function should be "GSAT". This function should take required three arguments in the following order: a sentence, the maximum number of restarts, and the maximum number of hill climbing steps. The function should return either a satisfying truth assignment for the atomic propositions, or NIL if none was found.

• Input sentences should take the form of pre-order parse trees of propositional logic sentences, implemented as nested lists. This input representation should support at least "AND", "OR", and "NOT, and it may also support "IMPLIES" and "EQUIV". For example, the sentence show in exercise 6.15 in the text should be encoded as the list:

  (and
(or P Q (not S))
(or (not P) Q R)
(or (not P) (not R) (not S))
(or P (not S) Tee))

  (Remember not to use "T" as a symbol, as this is a Lisp reserved word.)

• Your output truth assignments should take the form of an association list. This is a list of CONSes, with the CAR of each CONS being an atomic proposition name and the CDR of each CONS being its truth value, either T or NIL. Association lists may be easily searched using the Lisp ASSOC function.

• sat.lisp

Software Engineering Guidelines

Find errors as much as possible by rereading your code, not just by testing. Do not be satisfied as soon as your code seems to work. Continue looking for errors and making your code more elegant and concise until you are satisfied that it is likely to be completely correct.

Your code should be well-documented. This means that there should be comments explaining the purpose, inputs, and outputs of every non-trivial function or procedure that you write, and comments explaining any tricky parts of your code. You should write comments at the same time that you write the corresponding code. Comments added afterwards are rarely as useful.

Grade Statistics

------------------------------------------------------------
 Under Range    In Range  Over Range         Sum
           0          14           0    1208.000
------------------------------------------------------------
        Mean      Median    Midpoint   Geometric    Harmonic
      86.286      86.000      82.500      85.837      85.364
------------------------------------------------------------
          SD   Quart Dev       Range     SE mean
       8.888       6.000      33.000       2.375
------------------------------------------------------------
     Minimum  Quartile 1  Quartile 2  Quartile 3     Maximum
      66.000      81.000      86.000      93.000      99.000
------------------------------------------------------------
        Skew    Kurtosis
      -0.545       2.575
------------------------------------------------------------
   Null Mean           t    prob (t)           F    prob (F)
       0.000      36.326       0.000    1319.590       0.000
------------------------------------------------------------


Histogram:

       Midpt    Freq
      69.000       1 *
      75.000       1 *
      81.000       5 *****
      87.000       1 *
      93.000       4 ****
      99.000       2 **