CSE341 Key to Sample Final Exam         handout #19

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