Due Date: 11:59pm, Tuesday 28/Sept/04, using
try c325 a1 your_fileYou should submit one file containing all your programs along with documentation. Your programs will be run against our solutions and results generated. This may provide feedback to your work. You can keep submitting, and the last one before the deadline will be retained as your submission. Questions on the try command can be directed to email@example.com
Assignment Marks: There are a total of 65 marks possible on
this assignment. It is worth 8% of the total course grade.
Your programs must be readable and understandable as well as correct.
You should read the guidelines as given in programming
style and marking guideline.
You could lose up to 1/2 of the marks for bad style even if your
programs are correct.
(25/Sept: Changed "penalty for bad style", from 1/3 to 1/2, to be consistent with other documentation, and TA's earlier comments.)
You may only use the built-in Lisp functions and special forms shown here
You may write one or more functions to solve any given problem below. In some cases it is desirable to decompose a problem into smaller ones. However, if a problem has a straightforward single-function solution, it's a bad idea to solve it in a complex way by decomposition.
(my-min L)that returns the minimum value of the argument list-of-numbers L.
>(my-min '(3 1 -5 2)
(deep-member x y)that returns T if the first argument x appears anywhere at any level in the argument recursive-list y and NIL otherwise. This should test for lists being members of lists. Both the argument x and the list y may be NIL or lists containing NIL. See the examples. You cannot just call the built-in function member (see restrictions above).
>(deep-member '1 '(1) ) T >(deep-member '1 '( (1) 2 3) ) T >(deep-member '1 '( ((4 1)) 2 3) ) T >(deep-member '(1) '((1) 2 3) ) T >(deep-member nil nil) NIL >(deep-member nil '(nil) ) T >(deep-member nil '((nil) ) ) T >(deep-member '(nil) '(1 2 3 (nil)) ) T >(deep-member '(3) '(3) ) NIL
(deep-subst x y L)that returns returns a list L1 formed by replacing, within the recursive-list L, each occurance of the atom x (at any level) with the atom y.
>(deep-subst 4 t '(truth is 4))
(TRUTH IS T)
4 nil '(4 is not (4)))
(NIL IS not (NIL))
>(deep-subst 4 nil '(5 is not (22)))
(5 is not (22))
(lookup atom pair-list)that finds the "atom-entry" within the list of pairs pair-list, or NIL if atom does not match any of the entries in pair-list .
>(lookup '5 '((t frog) (5 what) (nil 1)))
>(lookup 5 '((1 this) (2 is) (3 a) (4 test)) )
cnf1 = (-x1 v -x2 v +x3) & (+x2 v +x4 v -x5)(We will later see that any boolean formula can be expressed as a CNF formula.)
assgn1 = ( (x1 t) (x2 nil) (x3 t) (x4 nil) (x5 t ) )maps x1 to T, x2 to NIL, x3 to T, x4 to NIL and x5 to T.
(-x1 v -x2 v +x3)
evaluates to T as its 2nd literal, -x2, evaluates to T as assgn1 includes (x2 nil).
(+x2 v +x4 v -x5)evaluates to NIL as each of its 3 literals evaluates to NIL.
(eval-cnf cnf assgn)that evaluates the boolean CNF formula cnf formula, with respect to the assignment assgn, returning T if assgn satisfies cnf, and NIL otherwise.
(+x1 v -x2 v +x3) & (+x2 v +x4 v -x5)as
( ((+ x1) (- x2) (+ x3)) ((+ x2) (+ x4) (- x5)) )As shown above, we represent an assignment as a list of (variable value) pairs; see assgn1 above.
> (eval-cnf '() '((a t))) T > (eval-cnf '(() ((+ a)) ) '((a t))) NIL > (eval-cnf '( ((+ a)) ) '((a t))) T > (eval-cnf '( ((+ a)) ) '((a nil))) NIL > (eval-cnf '( ((+ a) (- a)) ) '((a nil))) T > (eval-cnf '( ((+ a) (- b)) ) '((a nil)(b nil))) T > (eval-cnf '( ((+ a) (- b)) ((- a)) ) '((a nil)(b nil))) T > (eval-cnf '( ((+ a) (- b)) ((+ a)) ) '((a nil)(b nil))) NIL
that returns a satisfying assignment
if the CNF formula cnf
is satisfiable, and otherwise return NIL.
This function should use the simple "generate and test" approach: successively generate each possible assignments to the variables, then test if that assignment satisfies the CNF formula -- ie, if it makes the CNF true (hint: think eval-cnf).
Given a list of the variables in the formula, there is a simple recursive way to walk through the set of all assignments. You need only generate one assignment -- ie, your function should terminate on finding a satisfying assignment.
> (sat '( ((+ a)) ) ) ((a t)) > (sat '( ((+ a)) ((- a)) ) ) NIL > (sat '( ((+ a)) ((- b)) ) ) ((a t) (b nil)) > (sat '( ((+ a) (+ b)) ((- b)) ) ) ((a t) (b nil)) ;; ORIG: (a->b) & (b->c) & (c->-a) ;; (~a v b) & (~b v c) & (~c v ~ a) ;; CNF + ( (~a b) (~b c) (~c ~a) ) > (sat '( ((- a) (+ b)) ((- b) (+ c)) ((- c) (- a)) ) ) ((A NIL) (B T) (C T)) ;; a->b, b->c, c-> d > (sat '( ((- a ) (+ b)) ((- b) (+ c)) ((- c) (+ d)) ) ) ( (a t) (b t) (c t) (d t)) ;; a <=> b, -a , b ;; a-> b, b->a, -a, b > (sat '( ((- a) (+ b)) ((- b) (+ a)) ((- a)) ((+ b)) ) ) nil