<![CDATA[
CSE413 Key to Final Exam handout #11
1. Scheme expressions.
Part A:
(define a 2)
(define b 5)
(define c 10)
(let ((b (+ a b))
(c (+ b c)))
(+ a b c))
24
Part B:
(define a 2)
(define b 5)
(define c 10)
(let* ((b (+ a b))
(c (+ b c)))
(+ a b c))
26
Part C:
(define (g n) (f (+ n 2)))
(define (f n) (* n 3))
(define a (g 3))
(define b (f 3))
(define c a)
(set! a 42)
(list a b c)
'(42 9 15)
Part D:
(define a '(a b))
(define b '(a b))
(define c (list a b))
(define d (append a b))
(list c d (eq? a (car c)) (eq? b (cadr c)) (eq? b (cddr d)))
'(((a b) (a b)) (a b a b) #t #t #t)
2. Two possible solutions appear below.
(define (prepend x lst)
(map (lambda (y) (cons x y)) lst))
(define (prepend x lst)
(if (null? lst)
'()
(cons (cons x (car lst)) (prepend x (cdr lst)))))
3. Two possible solutions appear below.
(define (difference lst1 lst2)
(filter (lambda (n) (not (member n lst2))) lst1))
(define (difference lst1 lst2)
(cond ((null? lst1) '())
((member (car lst1) lst2) (difference (cdr lst1) lst2))
(else (cons (car lst1) (difference (cdr lst1) lst2)))))
4. One possible solution appears below.
(define (prefix lst1 lst2)
(cond ((null? lst1) #t)
((null? lst2) #f)
((equal? (car lst1) (car lst2)) (prefix (cdr lst1) (cdr lst2)))
(else #f)))
5. Two possible solutions appear below.
(define (multiples lst)
(map (lambda (n)
(length (filter (lambda (m) (= (modulo m n) 0)) lst))) lst))
(define (count-multiples n lst)
(cond ((null? lst) 0)
((= (modulo (car lst) n) 0)
(+ 1 (count-multiples n (cdr lst))))
(else (count-multiples n (cdr lst)))))
(define (multiples lst)
(define (explore short)
(if (null? short)
'()
(cons (count-multiples (car short) lst)
(explore (cdr short)))))
(explore lst))
6. One possible solution appears below.
(define (choose n lst)
(cond ((< n 0) (error "illegal argument"))
((= n 0) '(()))
((< (length lst) n) '())
(else (append (prepend (car lst) (choose (- n 1) (cdr lst)))
(choose n (cdr lst))))))
7. Ruby expressions.
Part A:
x.each {|n| puts 2 * n - 1}
5
15
17
13
7
9
Part B:
y.each {|n| puts n * x[n]}
18
21
16
Part C:
sum = 0
y.each do |n|
sum += n
puts n
end
puts sum
2
3
4
9
Part D:
x.map {|n| [n, n]}
[[3, 3], [8, 8], [9, 9], [7, 7], [4, 4], [5, 5]]
8. One possible solution appears below.
def match(lst1, lst2)
result = []
i = 0
while i < lst1.length && i < lst2.length
if lst1[i] == lst2[i]
result.push(lst1[i])
end
i += 1
end
return result
end
9. One possible solution appears below.
def unique(lst)
result = []
for i in lst
if !result.member? i
result.push i
end
end
return result
end
10. One possible solution appears below.
def split(lst, n)
result = []
n.times {result.push []}
for i in 0..(lst.length - 1)
result[i % n].push lst[i]
end
return result
end
11. One possible solution appears below.
class Array
def values
result = unique(self)
for i in result
count = 0
for j in self
if i == j
count += 1
end
end
yield i, count
end
result.length
end
end
]]>