CS3 Midterm Review Answers

More complicated recursion

1. (define (uncompress sent)
(if (empty? sent)
sent
(se (copies (first sent) (second sent))
(uncompress (bf (bf sent))))))

(define (copies num wd)
(if (= num 0)
'()
(se wd (copies (- num 1) wd))))

2. (define (longest-decreasing sent)
(if (empty? sent)
0
(max (decreasing-seq sent)
(longest-decreasing (bf sent)))))

(define (decreasing-seq sent)
(cond ((empty? (bf sent)) 1)
((<= (first sent) (second sent)) 1)
(else (+ 1 (decreasing-seq (bf sent))))))

3. (define (subsets sent)
(enumerate "" sent))

(define (enumerate sofar sent)
(if (empty? sent)
sofar
(se (enumerate sofar (bf sent))
(enumerate (word sofar (first sent)) (bf sent)))))

4. (define (snack c d)
(cond ((= c 0) 1)
((= d 0) 1)
(else (+ (snack (- c 1) d)
(snack c (- d 1))))))

Higher-Order-Functions

5. (define (add-digit num sent)
(every (lambda (wd) (word wd num))
sent)

6. (define (mode sent)
(accumulate
(lambda (a b)
(if (> (appearances a sent) (appearances b sent))
a
b))
sent))

7. (define (age student)
(keep number? Student))

(define (all-ages students)
(every age students))

8. (define (name student)
(accumulate
(lambda (a b)
(if (equal? a ',)
""
(word a b)))
student))

(define (oldest students)
(name (accumulate
(lambda (a b)
(if (> (age a) (age b))
a
b))
students)))

9. (define (downup wd)
(accumulate (lambda (letter sent)
(se (word (first sent) letter)
sent
(word (first sent) letter)))
(reverse wd)))

Lambda

10. This returns a procedure. Specifically,
(lambda (a b)
(+ a (* b 10) 5 8))

11. (((lambda (x y)
(lambda (a b)
(+ a
((lambda (g h)(* g h)) b 10)
x y)))
5 8)
10 7)

This return 93.

12. (define (categorize names)
(every
(lambda (letter)
(keep
(lambda (wd) (equal? (first wd) letter))
names))
'ABCDEFGHIJKLMNOPQRSTUVWXYZ))