CSE 352
Spring 2003
Stony Brook
Artificial Intelligence
Annie Liu
Assignment 2
Handout A2
Jan. 30, 2003
Due Feb. 6


Programming Recursion and Symbolic Manipulation

You are given a list of problems, together with programs for solving them in Lisp. Your task is to write programs for these problems in Java and compare your Java programs with the given Lisp Programs. You will be graded on the source code as well as all supporting documents. Remember that programming assignments are to be done in pairs.

All your Java code for the given problems should be put in one file and be well-commented or clearly self-explanatory. You should also provide code for testing your programs as automatically as possible and include instructions for demo/testing. Your comparison should include measures for code size and code clarity (such as, number of commented/uncommented characters/lines, ration of comments, and other good measures you can think of) for each problem.

Submission

Submit a printout of your Java source code and your description of the comparison in class on the due date, preferably printed 2 pages per sheet. Email cse352ATcsDOTsunysbDOTedu before that a .zip file that contains all your code and documents. Details regarding the .zip file:

Grading

This homework is worth 5% of the course grade. Exceptionally well-thought-out and well-written homeworks will receive appropriate extra credit. Excellent and additional work for the comparison (such as comparison of performance figures for the Java and Lisp programs) will received substantial extra credit.

Problems

Some of these are not easy to write, but the Lisp code contains good hints.

  1. Exponentiation. Write a recursive function two-to-the(x) which takes a single non-negative integer parameter x and returns 2x. (This can be done in logarithmic time.)

  2. Tree counting. Write a function count-trees(n) which returns the number of distinct strictly binary trees with n leaves. A strictly binary tree is one in which every node other than a leaf has exactly two children. A leaf has no children. There is 1 strictly binary tree with 1 leaf (just a single node tree), 1 strictly binary tree with 2 leaves, 2 distinct strictly binary trees with 3 leaves, and 5 distinct strictly binary trees with exactly 4 leaves. count-trees can be implemented fairly easily using recursion. Test your program for n = 1 through 10.
    [Hint: Suppose a tree with n leaves has a leaves in its left subtree and b leaves in its right subtree, where a+b=n; how many such trees are there?]

  3. Symbolic differentiation. One important AI application area is symbolic mathematics, particularly calculus. For this problem, you will construct a function deriv which differentiates simple, single-variable mathematical expressions. The function takes two arguments. The first is a mathematical expression in any syntax you feel most convenient, containing numbers, atoms (representing constants and variables) and the binary functions +,-,*,/,expt. The second is the name of the variable with respect to which to differentiate. Other symbols in the expression are treated as constants. The rules of differentiation are as follows (where u and v are arbitrary expressions): u = constant implies du/dx = 0
    dx/dx=1
    d(u+v)/dx = du/dx + dv/dx; d(u-v)/dx = du/dx - dv/dx
    d(uv)/dx = udv/dx + vdu/dx
    d(u/v)/dx = (vdu/dx - udv/dx)/v
    2
    v = constant implies d(uv)/dx = (du/dx)vu(v-1)
    d(eu)/dx = (du/dx)eu
    Test your function on some interesting inputs. Add more rules (e.g., for trig functions) if you wish. For extra brownie points, you can write a simplifier to reduce the resulting expressions to their simplest form. For example, 0 * u simplifies to 0 and so on.

  4. List recursion. Write the following functions:
    last-element(l) returns the last element of l;
    all-but-last(l) returns all but the last element;
    middle(l) returns the middle element, assuming an odd number of elements.
    Don't use any numbers to implement middle.

  5. Powerset. A standard mathematical set function is powerset, which computes the set of all subsets of a set. For example, powerset of {a,b} is {{}, {a}, {b}, {a,b}} Implement this as a recursive function. It may require other subsidiary functions.

  6. Points and lines. Write Java classes for points and line segments in two dimensions, and write the following functions distance(p1,p2) returns the distance between two points.
    midpoint(l) returns the midpoint of a line segment.
    intersectp(l1,l2) decides if two line segments intersect.

    [Hint for intersectp: the location of an arbitrary point on AB can be written as vA + (1-v)B; a point on CD is wC +(1-w)D; the lines cross where these are equal. This gives two equations (equating both x and y parts) for v and w. Solve these to find the intersection point, if any. Then you need to check that the intersection is actually on both segments - this can be determined by looking at the values of v and w.]

Programs in Lisp (Allegro Common Lisp)

;;; Problem 1 : POWERS OF TWO

;;; The basic, slow solution.
;;; Finds two-to-the by recursion on the size of the argument. 
(defun two-to-the (n)
  (if (= n 0) 1                   ; base case: 2^0 = 1
    (* 2 (two-to-the (- n 1)))))  ; recursive case: 2^n = 2*2^(n-1)

;;; The fast solution. 
;;; The problem size is halved with each recursion, since, for even n, 
;;; 2^n = (2^n/2)^2. (For odd n, n/2 must be rounded down: this is 
;;; made up for my multiplying the right hand side by an extra 2.)
(defun two-to-the-fast (n) 
  (if (= n 0) 1                     ; base case: 2^0 = 1
    (let ((two-to-half (two-to-the-fast (truncate n 2))))
      (if (oddp n)
        (* 2 two-to-half two-to-half) 
        (* two-to-half two-to-half)))))
  

;;; Problem 2 : DISTINCT STRICTLY BINARY TREES

;;; Recursive function to find # of distinct strictly binary trees w/ n leaves
;;; To find all possible sbt's with n leaves:
;;;     1) for a tree with left-n leaves in the left subtree and right-n
;;;        leaves in the right subtree, multiply
;;;        (count-trees left-n) by (count-trees right-n)
;;;     2) for n leaves, left-n ranges from 1 to n-1
;;;                  and right-n ranges from n-1 to 1
;;;     3) sum up the possible trees for each pair left-n, right-n
(defun count-trees (n &aux (total 0))
  (cond ((= n 1) 1)
        (t (loop for left-n from 1 to (- n 1) do
             (let ((right-n (- n left-n)))
               (setq total (+ total (count-trees-fixed-split left-n right-n)))))
           total)))

(defun count-trees-fixed-split (left-n right-n)
  (* (count-trees left-n) (count-trees right-n)))

;;; Here is a purely recursive version without the use of "loop"
(defun count-trees-recursive (n)
  (if (= n 1) 1
    (count-trees2 n (- n 1))))

(defun count-trees2 (n left-n)
  (if (= left-n 0) 0
    (let ((right-n (- n left-n)))
      (+ (count-trees-fixed-split left-n right-n)
         (count-trees2 n (- left-n 1))))))

;;; Here are the results for n from 1 to 10:
;1 
;1 
;2 
;5 
;14 
;42 
;132 
;429 
;1430 
;4862 
;;; You may notice that the algorithm runs very slowly. This is because it
;;; is computing the same results over and over. For example,
;;; (count-trees 5) calls (count-trees 4) and (count-trees 3),
;;; but (count-trees 4) also calls (count-trees 3), and so on.
;;; The "dynamic programming" approach is to build up a table
;;; of values for n = 1, 2, 3 and so on. When computing the next
;;; value, we already have available all the previous values so there 
;;; is no recomputation.


;;; Problem 3 : SYMBOLIC DIFFERENTIATION

;;; deriv simply moves recursively through the mathematical expression, 
;;; constructing the derivative expression.
;;; All the cases specified in the assignment are tested for using a 
;;; single cond statement.
;;; NB: The expressions returned by this will not be in their simplest form.
;;; For example:
;;; > (deriv '(* x x) 'x)
;;; (+ (* X 1) (* X 1))
;;; > (deriv '(expt x 2) 'x)
;;; (* 1 2 (EXPT X 1))

(defun deriv (expr var)
  (cond
   ((atom expr)              ; atom means either the variable or a constant.
     (if (eq expr var) 1 0)) 
   ((eq (first expr) '+)     
     (cons '+ (mapcar #'(lambda (x) (deriv x var)) (rest expr)))) 
   ((eq (first expr) '-)
     (cons '- (mapcar #'(lambda (x) (deriv x var)) (rest expr))))
   ((eq (first expr) '*)
     (list '+ (list '* (second expr) (deriv (third expr) var))
              (list '* (third expr) (deriv (second expr) var))))
   ((eq (first expr) '/)
     (list '/ (list '- (list '* (third expr) (deriv (second expr) var))
                       (list '* (second expr) (deriv (third expr) var)))     
              (list 'expt (third expr) 2)))
   ((eq (first expr) 'expt)
     (if (and (atom (third expr)) (not (eq (third expr) var)))
       (list '* (deriv (second expr) var) (third expr)
                (list 'expt (second expr) (- (third expr) 1)))))
   ((eq (first expr) 'exp)
     (list '* (deriv (second expr) var) expr))))


;;; Problem 4 : LIST RECURSIONS

;;; last-element simply moves recursively down the list until the last 
;;; element (the one with cdr = nil) is reached, and returns this element.
(defun last-element (l)
  (cond 
    ((null l) nil)                 ; this is a somewhat arbitrary convention
    ((atom l) (error "Argument not a proper list - last-element"))
                                   ; error check - this is optional
    ((null (cdr l)) (car l))       ; if this is the last element, return it.
    (t (last-element (cdr l)))))   ; else, recursion.

;;; all-but-last simply moves recursively down the list, building a new
;;; list of all the elements it encounters except the last one.
(defun all-but-last (l)
  (cond 
    ((null l) nil)                 ; this is a somewhat arbitrary convention
    ((atom l) (error "Argument not a proper list - all-but-last"))
                                   ; error check - this is optional
    ((null (cdr l)) nil)           ; if this is the last element, return nil.
    (t (cons (car l)               ; else add the current element to the list.
        (all-but-last (cdr l))))))

;;; middle simply recusively chops off the first and last elements of 
;;; the list, using cdr and all-but-last.
;;; NB: works only for lists with an odd number of elements.
(defun middle (l)
  (cond
    ((null l) nil)                 ; this is a somewhat arbitrary convention
    ((atom l) (error "Argument not a proper list - middle"))
                                   ; error check - this is optional
    ((null (cdr l)) (car l))       ; if one element is left, return it
    (t (middle (all-but-last (cdr l))))))

;;; This version of middle works in linear time (scans the list once)
;;; and constant space (keeps track of two list positions).
;;; The idea behind it is to have two pointers walk down the list,
;;; one (end-pointer) two times faster than the other (middle-pointer.)
;;; Thus, when end-pointer reaches the final element of the list,
;;; middle-pointer will be at the middle element: and if end-pointer walks
;;; past the final element (points to nil) the list must have had
;;; an even number of elements, and nil is returned. 
(defun fast-middle (l)
  (fast-middle2 l l))
(defun fast-middle2 (slow fast)
  (cond ((null fast) nil)          ; this is a somewhat arbitrary convention
        ((atom fast) (error "Argument not a proper list - fast-middle"))
                                   ; error check - this is optional
        ((null (cdr fast)) (car slow))  ; found the middle
        (t (fast-middle2 (cdr slow) (cddr fast)))))


;;; Problem 5 : POWERSET

;;; The key here is to consider the relationship between the
;;; powerset of s and the powerset of (cdr s).
;;; E.g., the powerset of (a b c) contains 8 elements:
;;;             ()    (b)   (c)   (b c)
;;;            (a)  (a b) (a c) (a b c)
;;; I.e., we can take each element of the powerset of (cdr s)
;;; and then have a choice of whether or not to include (car s) in it.
;;; The other thing to look out for is the base case: the powerset of 
;;; the empty set has one element, namely the empty set.
;;; Testing:
;;; > (powerset '(a b c))
;;; (NIL (C) (B) (B C) (A) (A C) (A B) (A B C))

(defun powerset (s)
  (if (null s) (list nil)        ; base case: (powerset '()) = '(())
    (let ((cdr-powerset (powerset (cdr s))))
      (append cdr-powerset
              (mapcar #'(lambda (subset) (cons (car s) subset)) 
                      cdr-powerset)))))


;;; Problem 6 : STRUCTURES

;; a. Definitions of point and seg (line segment.)
(defstruct point 
  x 
  y)

(defstruct seg 
  (p1 :type point) 
  (p2 :type point) )


;; b. distance calculates the distance between two points
;; using Pythagoras' theorem.
(defun distance (p1 p2)
    (sqrt (+ (square (- (point-x p1) (point-x p2)))
             (square (- (point-y p1) (point-y p2))))))

(defun square (x) (* x x))

;; c. the midpoint of a line segment l lies half way between its endpoints
;; on both the x and the y axis.
(defun midpoint (l)
    (make-point :x (/ (+ (point-x (seg-p1 l)) (point-x (seg-p2 l))) 2)
                :y (/ (+ (point-y (seg-p1 l)) (point-y (seg-p2 l))) 2)))

;; d.
;;; Intersectp finds the coordinates of the two segments endpoints,
;;; and uses them to calculate the values of v and w.
;;; Note that we need to check for the case where the lines are
;;; parallel, which would give a divide-by-zero error in the
;;; expressions for v and w.
;;; If v and w are both in the range [0,1], return the point
;;; of intersection (an example of a useful truth value.)

(defun intersectp (l1 l2)
    (let* ( (x1 (point-x (seg-p1 l1))) (y1 (point-y (seg-p1 l1)))
            (x2 (point-x (seg-p2 l1))) (y2 (point-y (seg-p2 l1)))
            (x3 (point-x (seg-p1 l2))) (y3 (point-y (seg-p1 l2)))
            (x4 (point-x (seg-p2 l2))) (y4 (point-y (seg-p2 l2)))
            (d (- (* (- x3 x4) (- y1 y2)) (* (- x1 x2) (- y3 y4)))))
      (if (zerop d)
          nil   ;;; lines are parallel - no intersection
        (let ((v (/ (- (* (- x2 x4) (- y3 y4)) (* (- x3 x4) (- y2 y4))) d))
              (w (/ (- (* (- x2 x4) (- y1 y2)) (* (- x1 x2) (- y2 y4))) d)))
          ;;; is the intersection inside the line segments?
          (if (and (>= v 0) (<= v 1) (>= w 0) (<= w 1)) 
              (make-point :x (+ (* v x1) (* (- 1 v) x2))
                          :y (+ (* v y1) (* (- 1 v) y2)))
            nil)))))

;;; Testing a case where the line segments intersect:
; > (intersectp (make-seg :p1 (make-point :x 0 :y 0) :p2 (make-point :x 2 :y 2))
;             (make-seg :p1 (make-point :x 1 :y 0) :p2 (make-point :x 1 :y 3)))
; #S(POINT :X 1 :Y 1)
;;; Testing a case where the lines are parallel:
; >  (intersectp (make-seg :p1 (make-point :x 0 :y 0) :p2 (make-point :x 2 :y 2))
;              (make-seg :p1 (make-point :x 1 :y 0) :p2 (make-point :x 4 :y 3)))
; NIL
;;; Testing a case where the intersection is outside the segments:
; > (intersectp (make-seg :p1 (make-point :x 0 :y 0) :p2 (make-point :x 2 :y 2))
;               (make-seg :p1 (make-point :x 1 :y 0) :p2 (make-point :x 1 :y -1)))
; NIL

Thanks to Professor Stuart Russet for all the problems and solutions.