CSE 471, Fall 2012, Introduction to Artificial Intelligence
Assignment 0, Lisp refresher. Due Jan 19th, 2012. In class.

People entering CSE471/598 vary widely in their LISP experience. All CS undergraduate students are supposed to have taken CSE 240, which would have given them a one-third semester exposure to Lisp. Some of the graduate students or students who asked for special permission may have some what lesser background in lisp. this assignment should serve as a refresher and an opportunity to become more familiar with Common Lisp (and will also give me an idea as to where the common denominator is for the class). While those who complete all these problems should have no trouble with projects, please don't think that if you cannot do all these problems, you have to drop the class. The coding required for actual projects will increase gradually rather than all at once.

Grading on this assignment will be soft. I expect everyone to try all of these questions, and if you submit your work, you get full credit. Indicate how much time you spent (max 6 hours recommended). With each solution, submit a transcript that demonstrates your code in action: try each function out with some different inputs.

Do's: recursion, comments, meaningful variable names

Don'ts: setq/setf, global variables
(Go low on these..)

1. Exponentiation
   Write a recursive function two-to-the which takes a single non-negative integer parameter x and returns 2^x. (This can be done in logarithmic time.)
   
   
2. 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. A definition of middle using cdr and all-but-last uses quadratic time and space; you can try to write a version that uses linear time and constant space (tricky).
   
   
3. Powerset
   A standard mathematical set function is 'powerset', which computes the set of all subsets of a set. Powerset of the set (A B) is ( () (A) (B) (A B)). Write a 'powerset' function. It may require other subsidiary functions.
   
   

4. List processing
   Write a function fringe that takes a list as argument and returns a list whose elements are all the atoms appearing in the original list or any of its sublists, arranged in left-to-right order. For example,

   ? (setf x (cons (list 1 2) (list 3 4)))
   ((1 2) 3 4)
   ? (fringe x)
   (1 2 3 4)
   ? (fringe (list x x))
   (1 2 3 4 1 2 3 4)
   

5. Data types
   (a) Write defstructs for points and line segments in two dimensions.
   (b) Write a function (distance p1 p2) that returns the distance between two points.
   (c) Write a function (midpoint l) that returns the midpoint of a line segment.
   (d)(optional) Write a function (intersectp l1 l2) that decides if two line segments intersect. [Hint: 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.]
   

6. Finding a Cube Root by Newton's Method
   Write a function newt-root which computes the cube root of a number, accurate to within a given tolerance, by Newton's method. Newton's method can be used to find the roots (zero-crossings) of any continuous differentiable function f(x).
   The algorithm for Newton's method is:
   1. Make an estimate x_o of the correct solution.
   2. Check to see if the value of f applied to the current estimate is sufficiently close to 0. If so, stop.
   3. Otherwise, compute a new estimate using the following formula: x_n+1 = x_n - f(x_n)/f'(x_n).
   4. Go to step 2.
   To find the cube root of a number a one applies Newton's method to the polynomial f(x) = x³-a. f'(x) is thus always 3x².
   
   
7. (Opt) 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 standard LISP syntax, containing numbers, atoms (representing constants and variables) and the binary functions +,-,*,/,expt. The second is the name of the variable over 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²
   v = constant implies d(u^v)/dx = (du/dx)vu^(v-1)
   d(e^u)/dx = (du/dx)e^u
   
   Test your function on some interesting inputs. You need not simplify the resulting expressions unless you are feeling particularly hyperactive. For extra brownie points, you can uses your symbolic differentiator with Newton's method to find roots of any function of x.
   
   
8. (Opt) Generating programs...!
   Write a function, called wheres-waldo, that takes a lisp object (i.e., a data structure built from conses) as argument and returns a Lisp expression that extracts the symbol waldo from this object, if it is present. For example,

   ? (wheres-waldo '(ralph waldo emerson))
   (FIRST (REST '(RALPH WALDO EMERSON)))
   
   Note that if we evaluate this expression, we get waldo, 
   
   ? (first (rest '(ralph waldo emerson)))
   WALDO
   ? (eval (wheres-waldo '(ralph waldo emerson)))
   WALDO
   
   In general, (eval (wheres-waldo x)) should return waldo if waldo is
   anywhere in x, and nil otherwise. Some more examples:
   
   ? (wheres-waldo '(emerson ralph waldo))
   (FIRST (REST (REST '(EMERSON RALPH WALDO))))
   ? (wheres-waldo
      '(mentor (ralph waldo emerson) (henry david thoreau)))
   (FIRST (REST (FIRST (REST 
                        '(MENTOR (RALPH WALDO EMERSON)
                                 (HENRY DAVID THOREAU))))))
   ? (wheres-waldo '(henry david thoreau))
   NIL