Assignment 1

Last updated 12 September 2010

See also: Assignment1FAQ with questions I've been asked and answers I've given.

Due Friday 17 February on paper in class and by email to LAS with the clearly labeled subject line FOCS assignment 1.

(If you do it on paper, use the handy dandy scanner/copiers to email ...)

This assignment is complete and officially released (as of 9:15pm Sunday 12 Sept).

1. Define the following procedures using only the basic numeric operations + - * / < > <= >= = and list manipulations (cons/car/cdr -- or first/rest if you prefer -- and empty?, which is sometimes spelled null?). You may also use the special forms (including define, lambda, and if) that we discussed in class.

1. A procedure that takes one argument, a positive integer, and returns the reciprocal (multiplicative inverse) of that number.

2. A procedure that takes one argument, a positive integer, and returns the factorial of that number.

3. A procedure that takes one argument, a positive integer, and returns a list of all of the integers between 1 and that number, inclusive.

4. Is your procedure (from 1c) tail-recursive/iterative? If so, why? If not, why not?

5. EXTRA CREDIT/CHALLENGE: Can you write this procedure (from 1c) two different ways, one tail-recursively and one not? (Hint: don't worry about the order of the numbers in the list you produce.)

2. Write a scheme procedure that takes a list of numbers and returns a list of the same numbers in ascending order. For example,

  (sort (list 3 1 7 5 -2 7 0 6))
  ==> (-2 0 1 3 5 6 7 7)

2. Is your procedure linear, quadratic, exponential, or something else? Explain your answer.

3. Suppose that we

•   (define repeatedly
      (lambda (f n)
        (lambda (x)
          (if (= n 0)
              x
              ((repeatedly f (- n 1)) (f x)))))) 

and also

•   (define 1+
      (lambda (x)
        (+ 1 x))) 

What will the results of evaluating the following expressions be?

1. ((repeatedly 1+ 6) 0)

2. ((repeatedly (repeatedly 1+ 3) 2) 1)

3. ((repeatedly (repeatedly 1+ 2) 3) 1)

4. ((repeatedly 1+ 3) ((repeatedly 1+ 2) 1))

5. (repeatedly (repeatedly 1+ 2) 3) 

6. Explain any differences among your answers.

7. EXTRA CREDIT/CHALLENGE Considering the definition of repeatedly, above, write a procedure repeatedly-until which takes a procedure f of one argument and a procedure until of one argument, and repeats f until until evaluates to true (on the same argument as f). Make sure that you return the final value of repeatedly applying f to x. For example,

   • ((repeatedly-until 1+ (lambda (x) 
                             (= (remainder x 10) 0)
                           )
      )
      346)
     
           ==> 350

4. Functional programming languages are quite good for some things, but less good for others. Read about (stacks and) queues in Cormen (pp. 200 - 203). Explain why a queue is a more natural fit for a procedural programming language (i.e., one that uses assignment as a common primitive) than for a purely functional programming language that does not use assignment. You may find it easier to answer this question if you think about implementing a queue in your favorite assignment-based programming language and in scheme. Your answer should be a few well reasoned sentences (no more than a paragraph), possibly with an accompanying illustration if it helps your explanation.

5. Extend our expression evaluator -- see ExpressionEvaluatorDotScm -- with each of the following operations. You may use any of the versions we discussed in class or your own.

1. Exponentiation. You may use scheme's exponentiation operator, expt, if you wish.

2. Squaring. Note that scheme does not have a built-in squaring operator.