EK 201 FINAL REVIEW NOTES:
    8-Dec-86 18:04:47

* The final will be in class WED DEC 10, 7:30PM->9:30PM

* To make up for the missed class there will be an optional
  field trip to see real industrial expert systems in action.
  Date: SAT DEC 13.
  Time: 1:30 PM
  Place: 1000 Mass Ave, Cambridge
         Across from the burned out Orson Welles Movie Theater.


* Review the Hand-Outs on Lisp Basics and Tree recursion.
  (Remember, this describes common-lisp as used in the
   Winston/Horn book, even though the homework assignments
   are dont in BU/vps lisp.)

  -> Basic Data types.
  -> List Structure
  -> EVAL, READ-EVAL-PRINT
  -> Building and manipulating lists.

* Review the Binary arithmetic examples and homework.
  Especially how to use the identities to construct
  recursive programs.

* Review the graph examples in the Winston/Horn book.

e.g.
          / E--------F
        /    \       |
     /--B-----C------G
   A           \
    \----------- D

represented as

(defprop a (b d) connections)
(defprop b (a c e) connections)
(defprop c (b d e g) connections)
(defprop d (a c) connections)
(defprop e (b c f) connections)
(defprop f (e g) connections)
(defprop g (c f) connections)

Then

(defun print-all-paths (from to)
  (ppath (list from) to))

(defun ppath (sofar goal)
  (cond ((eq (car sofar) goal)
	 (print (reverse sofar))
	 ())
	('else
	 (dolist (next (possible-routes sofar))
	   (ppath next goal)))))

(defun possible-routes (sofar)
  (let ((ok nil))
    (dolist (c (get (car sofar) 'connections))
      (or (memq c sofar)
	  (push (cons c sofar) ok)))
    (reverse ok)))

Now (print-all-paths 'a 'a)
will just print (A)
Q: how do we get it to print (a b c d a)?

What if we modify the end test in ppath:


(defun ppath (sofar goal)
  (dolist (next (possible-routes sofar))
    (cond ((eq (car next) goal)
	   (print (reverse next)))
	  ('else
	   (ppath next goal)))))

(defun possible-routes (sofar)
  (let ((ok nil))
    (dolist (c (get (car sofar) 'connections))
      (or (memq c (butlast sofar))
	  (push (cons c sofar) ok)))
    (reverse ok)))


We will get things like: (A B A) and (A B C D A).

(defun butlast (l)
  (cond ((null (cdr l))
	 nil)
	('else
	 (cons (car l) (butlast (cdr l))))))

Using butlast is not a very ellegant solution here.

Now, a path like (A B A) and (A B C D A)
are cycles, closed paths because they start and end
in the same place. Think about:

 * how would you modify these functions
   to get rid of paths such as (A B A), which
   back over themselves.


I like to think of this problem better as this:

(defun print-all-possible-loops (x)
  (dolist (y (get x 'connections))
    (print-all-paths y x)))

 * modify the code to return the paths as a list of paths
   instead of printing them.
 * you can get rid of (A B A) by getting rid of all paths 3 long.

Now, a cycle such as (A B C D A) is in a sense equal to (B C D A B).
They start and end in different place, but they cover the
same points in the same direction.

 * How would your write a CYCLE-EQUALP function?
 * How would you genera