CSE341 Sample Final Questions          handout #18

This is not an example of a complete final.  It is an example of the kind of
questions you can expect to be asked on the final.  The actual final will have
a few questions that are more difficult than these.

1. (10 points) For each sequence of Scheme expressions below, indicate what
   value the final expression evaluates to.

   (2 points) Part A:
        (define a 1)
        (define b 2)
        (define c 3)
        (let ((b (+ 2 4))
              (c (+ b 10)))
          (+ a b c))

   (2 points) Part B:
        (define a 3)
        (define b 4)
        (define c 5)
        (let* ((b (+ 2 4))
               (c (+ b 10)))
          (+ a b c))


   (3 points) Part C:
        (define a 1)
        (define b (list a 2))
        (set! a 3)
        (set-car! (cdr b) 4)
        (list a b)

   (3 points) Part D:
        (define a '(1 2))
        (define b (cons 3 a))
        (define c (append a b))
        (set-car! a 4)
        (list a b c)

2. (10 points) Define a Scheme procedure count that takes a value and a list as
   (count '(a b) '(a b c (a b) d 3 a b))(count '(a b) '(a b c (a b) d 3 a b))
   argument and that returns the number of occurrences of the value in the
   list.  Your procedure should use a deep equality comparison.  For example:

        > (count 3 '(7 9 2 4 a (3 2) 3 "hello" 3))
        2
        > (count 'a '(3 a b a 19 (a b) c a))
        3
        > (count '(a b) '(a b c (a b) d 3 a b))
        1

3. (10 points) Define a Scheme procedure zip that takes two lists as arguments
   and that returns the list obtained by combining pairs of values in
   corresponding positions into lists of 2 elements.  The first element should
   be a list containing the first values from each list.  The second element
   should be a list containing the second values frome each list.  And so on.
   If one list is shorter than the other, than zip should return a list of that
   shorter length.  For example:

        > (zip '(1 2 3) '(a b c))
        ((1 a) (2 b) (3 c))
        > (zip '(1 2 3 4 5) '(a b c d))
        ((1 a) (2 b) (3 c) (4 d))

4. (10 points) Define a Scheme procedure sum that a list as an argument and
   that returns the sum of all of the numbers contained in the list.  Your
   procedure should include all numbers in the list, even numbers contained in
   sublists.  For example:

        > (sum '(1 3 a 45.2 "hello" 7 -9))
        47.2
        > (sum '(3.4 (a b (c 2.4)) (a 1.2) 5.3))
        12.3

5. (10 points) Define a Ruby method posOf(shortList, longList) that returns the
   position of one array inside another array.  If the short array appears
   multiple times in the long array, your method should return the position of
   the first occurrence.  For example, given the call:

        posOf([1, 2], [7, 8, 1, 2, 7.9, "hello", 1, 2]) should return 2

   You may assume that both parameters are arrays and that the short array is
   not empty.  Your method should return -1 if the short array does not appear
   in the long array.

6. (10 points) Define a Ruby method commonFactors(n1, n2) that returns the
   common factors of two positive integers as an array in increasing order.
   You may use the factors iterator of assignment 8 in solving this problem.
   For example:

        commonFactors(24, 60) should return [1, 2, 3, 4, 6, 12]

   Your method should run in O(sqrt(min(n1, n2))) time.

7. (10 points) Define a Ruby class called Randomizer that takes two integer m
   and n as arguments when constructed and that has an each method that returns
   all of the values from m to n inclusive in a randomized order.  Each value
   in the range should be generated exactly once.  For example, the following
   code:

        r = Randomizer.new(1, 20)
        for i in r
            print i, " "
        end
        print "\n"

   would produce output like the following:

        5 9 7 11 2 15 3 13 12 17 8 18 1 14 20 19 10 4 16 6