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

- Exponentiation

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

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

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

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

- Data types

(a) Write`defstruct`s 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.]

- 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*of the correct solution._{o}

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*4. Go to step 2._{n}).

To find the cube root of a number*a*one applies Newton's method to the polynomial*f(x) = x*.^{3}-a*f**'**(x)*is thus always 3*x*^{2}.

- (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^{2 }*v =*constant*implies d(u*^{v})/dx = (du/dx)vu^{(v-}^{1) }*d(e*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.^{u})/dx = (du/dx)e^{u }

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