[FrontPage] [TitleIndex] [WordIndex

Assignment 1

Corrected Sat 4 Feb 2006 8:20pm

Due Monday 6 February by email to LAS and Sean (except for the programming project for 6 credit students, which is due Thursday 9 February).

If you do it on paper, use the handy dandy scanner/copiers in the AC and OC to email ... if you haven't tried them yet, you are in for a treat!

This assignment has been offically released and is ready to roll.

  1. Write a procedure that takes two lists of numbers in ascending order and produces a single, merged list also in ascending order. For example, {{{(merge (list 1 4 6 8 10) (list 2 3 5 8 18))

==> (1 2 3 4 5 6 8 8 10 18)}}}

  1. Is your procedure linear, quadratic, exponential, or something else? Explain your answer.
  1. Suppose that we

    (define apply-to-five
      (lambda (f)
        (f 5))) 

    and also

     (define 1+
       (lambda (x)
         (+ 1 x))) 
    What will the results of evaluating the following expressions be?
    1. (apply-to-five 1+)

    2. (apply-to-five (lambda (n) (* n 3))) 

    3. (apply-to-five apply-to-five) 

  2. 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 list of numbers, and returns the largest number in the list.
    2. A procedure that takes one argument, a list of numbers, and returns the arithmetic mean (what we lay folks call the average) of the numbers in the list.
    3. a procedure collect-stats that takes as an argument a list of numbers and returns a list of three numbers: the maximum value in the original list, the minimum value in the original list, and the arithmetic mean of the numbers in the original list.

  3. 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.
  4. Project students only: Also do 2006ProjectAssignment1 Turn in a code listing (.scm file, properly commented, in ascii so we can run it) and some examples of your code working.

  5. EXTRA CREDIT/CHALLENGE Define a procedure, {\tt repeatedly}, that takes two arguments -- f, a procedure of one argument, and n, a number of times to apply f -- and returns the function f composed with itself n times. For example, assuming the definition of 1+ from above, {{{((repeatedly 1+ 3) 6) 9}}}

    1. What are the values of the following expressions?
      1. ((repeatedly (lambda (x) (* x x)) 3) 2)

      2. ((repeatedly (repeatedly 1+ 4) 5) 200)

  6. EXTRA CREDIT/CHALLENGE Now write a procedure repeatedly-until which takes a procedure f of one argument and a procedure until of one argument, and repeats f}{{{until {\tt 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)


2013-07-17 10:42