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.
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