CSci 1901 Spring 2006

Thursday, February 15

50 minutes == 50 points

Open book and notes

- (10 points)
Show the values of the indicated expressions, assuming all the expressions are evaluated in order.

`(define a (cons 3 (cons 2 (list 4))))``(define (foo x) (cons (car x) '()))``a``(cadr a)``(cons 5 '())``(list 5)``(foo a)``(let ((z (cadr a)))``(cons 5 z))``((lambda (x) (cons 6 x)) '(8))``((lambda (x y) (* x (+ 1 y))) 4 2)` - (4 points)
Write a predicate

`(multipleof5? x)`that returns`#T`if`x`is a multiple of 5 and`#F`otherwise. It should work like this:`(multipleof5? 7)`*should return*`#F`*since 7 is not a multiple of 5*`(multipleof5? 35)`*should return*`#T`*since 35 is a multiple of 5* - (10 points)
Write a predicate

`(list-not-multipleof5 low high)`, where`low`and`high`are respectively the lower and the higher limit of an interval. The predicate should return the elements in the interval`low`to`high`that are not multiple of 5. Assume that`low`and`high`are positive integers and that . It should work like this:`(list-not-multipleof5 2 6)`*should return*`(2 3 4 6)`*since these are in the interval and are not multiple of 5*`(list-not-multipleof5 11 11)`*should return*`(11)`*since 11 is not a multiple of 5*`(list-not-multipleof5 10 10)`*should return*`()`*since no element in the interval is not a multiple of 5* - (10 points)
Write a procedure that takes a list as an argument and returns the list with each element divided by 2. It should work like this:

`(half '(2 4 8))`*should return*`(1 2 4)``(half '(1))`*should return*`(0.5)``(half '(10 20))`*should return*`(5 10)``(half '())`*should return*`()` - (10 points)
Write a predicate

`(some? pred l)`that returns`#T`if any element of the list`l`satisfies the predicate`pred`, and`#F`otherwise. It should work like this:`(some? odd? (list 2 6 3 8))`*should return*`#T`*since 3 is an odd number*`(some? divisibleby5? (list 1 17 32))`*should return*`#F`*since no element in the list is exactly divisible by 5* - (6 points)
What is the difference in the cost between the following two definitions of the modular exponentiation function

`expmod`? Which version below has fewer operations? Which version has smaller intermediate numbers? Explain. [Hint: consider the computation of`(expmod 10000 7777 3)`](a) (b) (define (expmod base exp m) (modulo (expt base exp) m)) (define (expt base exp) (if (= exp 0) 1 (* base (expt base (- exp 1)))))

`(define (expmod base exp m) (if (= exp 0) 1 (modulo (* base (expmod base (- exp 1) m)) m)))`