Written Assignment #3

1. Recall from class that in Lisp, functions, operations, and quantification are all represented as preorder lists. Thus the expression x+y is represented as (+ x y), x-y is represented as (- x y), and xy is represented as (* x y).
   1. What do the lists
      (+ 3 4 (* (+ a 2) (- x 3) z) (* 3 x y))
      and
      (+ -2 (- 2) (* X (+ Y 3.3)))
      represent in normal mathematical (infix) notation?
   2. How are the expressions xyz+3(u+v) and (xy-xz)(xy+z + 3u) to be represented in Lisp notation?
2. Using vertex-based representations for graphs, the list
   ((A B C D) (B A C) (C A B D) (D A C)) is used to represent the following graph:

   

   The same graph would be represented in edge-based form by the list
   ((A B) (A C) (A D) (B C) (C D)).

   1. Draw the graph represented by the list
      ((X Y E F) (Z Y E F) (Y X Z) (E X Z) (F X Z))
   2. what is the edge based representation for this graph?
3. Write the list (+ (* X Y Z) A 3) as an s-expression. This is sometimes referred to as ``dot-notation.''
4. Write the following s-expressions in list notation to whatever extent is possible:
   1. (A . NIL)
   2. (A . B)
   3. ((A . NIL) . B)
   4. ((A . ( B . ( C . NIL))) . NIL)
   5. ((A . B) . ((C . D) . NIL))
5. Draw each of the s-expressions in the previous exercise using box and arrow notation.
6. Draw the s-expressions resulting from the following lisp operations in box and arrow notation:
   1. (cons 'a nil)
   2. (cons 'a 'b)
   3. (cons 'a (cons 'b (cons 'c (cons 'd nil))))
   4. (cons (cons 'a nil) (cons 'b nil))
   5. (car (cons (cons 'a 'b) (cons 'c 'd)))
   6. (cdr (cons (cons 'a 'b) (cons 'c 'd)))
   7. (car (cons (cons 'a 'b) (car (cons 'c 'd))))
7. To access element X in the S-expression (X . ( Y . a)), you would need to perform the operation car. To access element Y, you would need to perform the operation car after applying operation cdr. What combinations of cars and cdrs are required to access the element X in each of these S-expressions?
   1. (( a . b) . X)
   2. (( X . b) . c)
   3. ( a . (( X . b) . c))
8. Write compound cons statements to construct the following s-expressions (which have been converted to list notation as far as possible):
   1. (a . (b . c))
   2. (a b c)
   3. (a b c (d . (e . f)))
   4. (a (b) (c . d) (( e . f) . g))

9. Assume for this problem and the next that X = (cons 'a 'b), Y = (cons 'c nil), and Z = (cons X Y)
   Draw each of the following in box and pointer notation:
   1. X, Y, and Z
   2. (cons X (cons 1 (cons X nil)))
   3. (cons X (cons (cons 'a 'b) X))
   4. (cons X (car Z))
10. T or nil (lisp's version of true or false):
    1. (equal X (car Z)
    2. (equal X (cons 'a 'b))
    3. (eq X (car Z))
    4. (eq X (cons 'a 'b))
    5. (atom X)
    6. (atom (car X))
    7. (null Y)
    8. (null (cdr Y))
    9. (atom (car (car (car (cons Z X)))))