CECS 375 Assignment 1:   Intro to Lisp

Due Friday, Sept. 12 by noon, Email your work to Matt Williams at mgw5a2@mizzou.edu

The assignment is worth 2% of your semester grade.

 

This assignment is a set of small lisp exercises.  The purpose is to give you some practice in writing lisp programs and prepare you for the AI assignments.  Include a test log showing that your program works on a sampling of different input conditions.  When coding, use recursion, choose meaningful variable names, and include comments.

 

  1. Write a recursive function (fibonacci n) to compute the first n Fibonaaci numbers in the sequence. Recall that the Fibonaaci sequence is defined as follows:  Fn = F n-2 + F n-1 for n=3,4,… with F1=F2=1.  The first few numbers in the sequence are 1, 1, 2, 3, 5, 8, 13.

 

  1. Write the following functions for manipulating lists:
    (first-elements x n) returns the first n elements of list x
    (nth-element x n) returns the nth element of list x
    (middle x) returns the middle element of list x, assuming an odd number of elements. If the list is even, then it returns the first of the two middle elements.   Don't use any numbers to implement middle.

 

  1. Write your own sort function (mysort x) that returns a sorted list of x in ascending order without changing the original list.

 

  1. Write defstructures for points and line segments in two dimensions.  Then write the following functions:
    (a) Write a function (distance p1 p2) that returns the distance between two points.
    (b) Write a function (midpoint k) that returns the midpoint of a line segment.
    (c) EXTRA CREDIT:  Write a function (intersectp k1 k2) 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.]