Key to CSE431 Sample Final handout #8 1. Scheme expressions. Part A: (define a 101) (define b 103) (define c 105) (let ((c (+ a c)) (a (+ b c))) (list a b c)) '(208 103 206) Part B: (define a 101) (define b 103) (define c 105) (let* ((b (+ a b)) (a (+ b c))) (list a b c)) '(309 204 105) Part C: (define x 101) (define (f n) (+ x y n)) (define y 103) (define a (f 2)) (define x 105) (define b (f 2)) (define c a) (set! a 19) (list a b c) '(19 210 206) Part D: (define a '(1 2 3)) (define b '(2 3)) (define c (append (cdr b) a)) (define d (list a b)) (list c (eq? a (car d)) (eq? (cdr a) b) (eq? (cdr c) a)) '((3 1 2 3) #t #f #t) 2. One possible solution appears below. (define (occurrences v lst) (length (filter (lambda (n) (equal? n v)) lst))) 3. One possible solution appears below. (define (remove-all v lst) (filter (lambda (n) (not (equal? n v))) lst)) 4. One possible solution appears below. (define (maximum lst) (define (explore max lst) (cond ((null? lst) max) ((> (car lst) max) (explore (car lst) (cdr lst))) (else (explore max (cdr lst))))) (if (null? lst) (error "max of empty list") (explore (car lst) (cdr lst)))) 5. One possible solution appears below. (define (pattern item) (cond ((number? item) 'number) ((string? item) 'string) ((symbol? item) 'symbol) ((boolean? item) 'boolean) ((list? item) (map pattern item)) (else item))) 6. One possible solution appears below. (define (switch-pairs lst) (cond ((not (list? lst)) (error "not a list")) ((null? lst) lst) ((null? (cdr lst)) lst) (else (cons (cadr lst) (cons (car lst) (switch-pairs (cddr lst))))))) 7. One possible solution appears below. (define (overlap lst1 lst2) (cond ((null? lst1) '()) ((null? lst2) '()) ((< (car lst1) (car lst2)) (overlap (cdr lst1) lst2)) ((> (car lst1) (car lst2)) (overlap lst1 (cdr lst2))) (else (cons (car lst1) (overlap (cdr lst1) (cdr lst2)))))) 8. One possible solution appears below. (define (histogram lst) (if (null? lst) lst (let ((v (car lst))) (cons (list v (occurrences v lst)) (histogram (remove-all v lst)))))) 9. Ruby expressions. Part A: x.each {|n| puts n + 2} 12 13 14 15 16 Part B: for n in y do puts n * 3 end 6 9 15 21 33 Part C: x.map {|n| n % 2 == 0} [true, false, true, false, true] 10. One possible solution appears below. def switch_pairs(list) result = [] i = 0 while i < list.length - 1 result << list[i + 1] result << list[i] i += 2 end if i < list.length result << list[i] end result end 11. One possible solution appears below. class Range def first(n=1) count = 0 for m in self break if count >= n count += 1 yield m end end end 12. One possible solution appears below. class Array def pairwise first = true for n in self if first old = n first = false else if !(yield(old, n)) return false end old = n end end true end end 13. One possible solution appears below. class Array def mode old = nil max = 0 max_v = nil count = 0 for v in self if v == old count += 1 else if count > max max = count max_v = old end old = v count = 1 end end if count > max [old, count] else [max_v, max] end end end
Stuart Reges
Last modified: Sat Mar 2 14:08:43 PST 2024