CAP5605/4601 Homework 1

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CAP5605/4601 Homework 1

Due: Jan 29, 11:59pm

DO NOT CONSULT ANY OUTSIDE REFERENCES OR SOURCES FOR THIS PROBLEM SET.

This is a programming assignment. For each of the questions, you need to submit a .clisp file, named “hw#_question#.clisp”. For example, for the first question you need to submit a filenamedhw1_1.clisp. Inside each of your clisp files, please include your name and FSUID in the first line as a comment.

You can ONLY use the functions we introduced in the class lectures for your lisp programming. You will receive 0 credit if you use loop or global variables.

Question 4 is the challenge question. It is optional for students in CAP4601, counting for 2 extra cred- its that will be applied to their total score.  It is mandatory for students in CAP5605.  Note that there are separate places for submitting the regular and challenge questions.

The questions 2-4 concern the famous Fibonacci sequence.  The first few elements of the sequence are 1 1 2 3 5 8 13 21 34 ... Each term is the sum of the two previous terms. This sequence is ubiquitous in nature.

1.  (10 pts) Write a single pure LISP function, called DMAX, that takes a single list argument X, and returns the deep maximum of the list X. For example (DMAX ’(1 (4 5) ((7 (8)) 4))) should return 8.

2.  (10 pts) Write a single pure LISP function, called FIB, that takes a single numeric argument N, and returns the Nth Fibonacci number. For example (FIB 3) should return 2. Test your program on at least the first 20 Fibonacci numbers. Also test your program for larger values of N. What happens? Why?

3.  (10 pts) Write a single pure LISP function, called SUMS, that takes a single numeric argument N, and returns the number of additions required by your FIB function to compute the Nth Fibonacci number. For example (SUMS 3) should return1. Design the recursion for SUMS by examining your FIB code.  SUMS should not call any auxiliary functions.  Test your program on at least the first  10 values.  What is the relationship between the values returned by FIB and SUMS? Explain why this is the case.

4.  (20 pts)  (Challenge) Write a purely applicative LISP program that computes the Nth Fibonacci number using approximately N additions. In other words, the running time of your program should be proportional to N. Write a top-level function, called FASTFIB, that takes a single numeric argument N, and returns the Nth Fibonacci number. You may define and use only one auxiliary function. Try to minimize the number of arguments to your functions. My solution uses only two single-argument functions. Note that you are not expected to develop a closed-form analytic expression for theNth Fibonacci number, but rather to formulate a recursive solution. Test your program for N = 1 through 10, and also 20, 30, 40, 50, 60, 70, 80, 90, and 100. Time the execution of your FIB function from part 1 and estimate how long your FIB function would take to compute the 100th Fibonacci number.

Submit 3+1 files with your commented code, and the answers to the questions asked above, via Canvas.  Be sure to name your functions the same as specified above, as they will be tested automatically.  Your programs should be written in good style. Provide an overall comment explaining your solutions. Any characters following a semicolon (;) on a line are treated as comments.