CSE 471/598 Spring 2004

Lisp Assignment

Assignment Due:  Feb. 10  (Tues), 2004, 5:00pm.

This assignment is for refreshing the students' Lisp basics and programming skills. There are 5 problems in this assignment. 3 problems are mandatory for everyone to submit and 2 problems are optional.

Required Programs

1. Input/Ouput

Write a function unique that takes in two strings, 'infile' and 'outfile' as parameters. 'infile' is the name of a file containing a sequence of words. The words are         separated by any combination of whitespace characters (space, newline, tab). Your function should read such a file, find the uniqe words in it and write it in a new file named 'outfile'.

CONSTRAINTS: All the words are case insensitive
CAUTION: Be careful with the path separators while specifying the filenames. For windows use "\\" as separator and for unix/linux use "/" as separator.

See sample input and output files for example.

2. List Recursion

Write a recursive function revert which takes a list 'l' as parameter and returns the reverse of the list. DO NOT use inbuilt function 'reverse'.
e.g., (revert '(a b c)) should return (C B A)

3. Using Structures

a) create a structure to define a point in cartesian co-ordinate system
b) create a structure to define a line segment in cartesian co-ordinate system
c) write function distance that take in two points as parameters and returns the euclidean distance between the points.
    Euclidean distance between points (x1, y1) and (x2, y2) is defined as
                                                                   
                                                            dist = sqrt((x1-x2)^2 + (y1-y2)^2)   

d) write a function midpoint that take a line segment as parameter and returns the midpoint (of point structure type) of the line segment.
     Midpoint of a line segment connecting two points (x1, y1) and (x2, y2) is given by
                                  
                                                            (midx, midy) = ((x1+x2)/2, (y1+y2)/2)

Optional Programs

4. Power of  2

Write a recursive function power-of-two which takes an integer parameter 'n' and returns 2^n. (This can be done in logarithmic time)

CONSTRAINTS: The parameter 'n' is non-negative
e.g., (power-of-two 10) should return 1024

5. Powerset

Write a function powerset that takes a list 'l' as input and returns the powerset of the list. Assume the input list as a set, and generate the powerset. A powerset is defined as a set of all subsets of a set.

CONSTRAINTS: The elements of parameter 'l' will be distinct
e.g., (powerset '(1 2 3)) should return the following
                                        (NIL (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))

HINT: powerset of {a, b, c, d,...} is equal to union of powerset of {b, c, d,...} and 'a' appended to each element of powerset of {b, c, d,...}
PS: The ordering of the sets in the powerset is not important.