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.
- 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)}}}
- Is your procedure linear, quadratic, exponential, or something else? Explain your answer.
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?(apply-to-five 1+)
(apply-to-five (lambda (n) (* n 3)))
(apply-to-five apply-to-five)
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.
- A procedure that takes one argument, a list of numbers, and returns the largest number in the list.
- 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.
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.
- 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.
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.
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}}}
- What are the values of the following expressions?
((repeatedly (lambda (x) (* x x)) 3) 2)
((repeatedly (repeatedly 1+ 4) 5) 200)
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)
350}}}