CSE341 Key to Sample Final Exam         handout #21

1. Scheme expressions.
   Part A:
        (define a 5)
	(define b 10)
	(define c 20)
	(let ((b (+ a c))
              (a (+ b c)))
          (list a b c))

        (30 25 20)

   Part B:
        (define a 5)
	(define b 10)
	(define c 20)
	(let* ((b (+ a c))
               (a (+ b c)))
          (list a b c))

        (45 25 20)

   Part C:
        (define x 10)
        (define (f n) (* x n))
        (define a (f 3))
        (define x 20)
        (define b (f 4))
        (define c a)
        (set! a 42)
        (list a b c)

        (42 80 30)

   Part D:
        (define a '(x y))
        (define b (cdr a))
        (define c (append b a))
        (define d (cons 'y '(a b)))
        (list c (eq? (cdr a) b) (eq? (cdr d) a) (eq? (cdr c) a))

        ((y x y) #t #f #t)

2. One possible solution appears below.

        (define (sum lst1 lst2)
          (cond ((null? lst1) lst2)
                ((null? lst2) lst1)
                (else (cons (+ (car lst1) (car lst2))
                        (sum (cdr lst1) (cdr lst2))))))

3. One possible solution appears below.

        (define (repeat n val)
          (define (explore m lst)
            (if (= m 0)
                lst
                (explore (- m 1) (cons val lst))))
          (if (< n 0)
              (error "negative argument")
              (explore n ())))

4. Two possible solutions appear below.

        (define (inflate lst)
          (if (null? lst)
              ()
              (append (repeat (caar lst) (cdar lst)) (inflate (cdr lst)))))o
        (inflate '((2 . 3) (5 . 14) (7 . 21)))
        (define (inflate lst)
          (foldr append () (map (lambda (x) (repeat (car x) (cdr x))) lst)))
        
5. One possible solution appears below.

        (define (same-structure x y)
          (cond ((or (null? x) (null? y)) (and (null? x) (null? y)))
                ((or (not (list? x)) (not (list? y)))
                 (and (not (list? x)) (not (list? y))))
                (else (and (same-structure (car x) (car y))
                           (same-structure (cdr x) (cdr y))))))

6. One possible solution appears below.

        (define (deflate lst)
          (define (explore value n lst)
            (cond ((null? lst) (list (cons n value)))
                  ((equal? (car lst) value) (explore value (+ n 1) (cdr lst)))
                  (else (cons (cons n value)
		              (explore (car lst) 1 (cdr lst))))))
          (if (null? lst)
              ()
              (explore (car lst) 1 (cdr lst))))

7. Two possible solutions appear below.

        (define (depth-count lst)
          (foldl sum '(0)
                 (map (lambda (x)
                        (if (not (list? x))
                            '(1) 
                            (cons 0 (depth-count x))))
                      lst)))
        
        (define (depth-count lst)
          (cond ((null? lst) '(0))
                ((not (list? (car lst))) (sum '(1) (depth-count (cdr lst))))
                (else (sum (cons 0 (depth-count (car lst)))
                           (depth-count (cdr lst))))))

8. Ruby expressions.

   Part A:
        x.each {|n| puts 2 * n + 1}

        3
        5
        7
        9
        11

   Part B:
        for n in y do
          puts n - 1
        end

        1
        3
        5
        7
        9
        11

   Part C:
        y.map {|n| [n]}

        [[2], [4], [6], [8], [10], [12]]

9. One possible solution appears below.

        def stretch(lst, n)
          result = []
          for x in lst
            n.times {result.push x}
          end
          result
        end

10. One possible solution appears below.

        class Array
          def every n
            i = n - 1
            while i < length
              yield self[i]
              i += n
            end
          end
        end

11. One possible solution appears below.

        class Array
          def for_index
            result = []
            for i in 0..(length - 1)
              result.push self[i] if yield(i)
            end
            result
          end
        end

12. Two possible solutions appear below.

        class String
          def same_pattern? (other)
            return false if length != other.length
            for i in 0..(length - 1)
              for j in 0..(length - 1)
                return false if (self[i] == self[j]) != (other[i] == other[j])
              end
            end
            return true
          end
        end

        class String
          def same_pattern? other
            return false if length != other.length
            map1 = {}
            map2 = {}
            for i in 0..(length-1)
              if map1[self[i]]
                return false if other[i] != map1[self[i]]
              else
                map1[self[i]] = other[i]
              end
              if map2[other[i]]
                return false if self[i] != map2[other[i]]
              else
                map2[other[i]] = self[i]
              end
            end
            return true
          end
        end