<![CDATA[
CSE341 Final
Winter 2007
Name of Student_______________________________________________________________
This is an open-book/open-note exam. Space is provided for your answers. Use
the backs of pages if necessary. The exam is divided into eleven questions
with the following distribution of points:
# Problem Area Points Score
-----------------------------------------------------
1 Scheme Expressions 10 _____
2 Scheme Programming 10 _____
3 Scheme Programming 10 _____
4 Scheme Programming 10 _____
5 Scheme Programming 10 _____
6 Scheme Programming 10 _____
7 Ruby Expressions 8 _____
8 Ruby Programming 8 _____
9 Ruby Programming 8 _____
10 Ruby Programming 8 _____
11 Ruby Programming 8 _____
----------------------------------
Total 100 _____
Do not begin work on this exam until instructed to do so. Any student who
starts early or who continues to work after time is called will receive a 10
point penalty.
Unless otherwise noted, you may use any standard language feature. You may
also define helper procedures/methods. For the Scheme questions, you may call
any Scheme procedure that is included as a problem on this exam, whether or not
you correctly solve that problem. For the Ruby questions, you may call any
Ruby method that is included as a problem on this exam, whether or not you
correctly solve that problem.
1. (10 points) For each sequence of Scheme expressions below, indicate what
value the final expression evaluates to.
(2 points) Part A:
(define a 2)
(define b 5)
(define c 10)
(let ((b (+ a b))
(c (+ b c)))
(+ a b c))
(2 points) Part B:
(define a 2)
(define b 5)
(define c 10)
(let* ((b (+ a b))
(c (+ b c)))
(+ a b c))
(3 points) Part C:
(define a 'b)
(define b (cons a '(a b)))
(set! a 1)
(set-car! (cdr (cdr b)) 2)
(list a b)
(3 points) Part D:
(define a '(1 2))
(define b (cons 4 a))
(define c (append b a))
(set-cdr! a '(3))
(set-car! b 5)
(list a b c)
2. (10 points) Define a Scheme procedure prepend that takes a value and a list
of lists as arguments and that returns a new list obtained by inserting the
given value at the front of each list within the list of lists. For
example:
> (prepend 'a '((b c) (2 3 4) (9) () (17 x y)))
((a b c) (a 2 3 4) (a 9) (a) (a 17 x y))
Your procedure should not change the list passed as a parameter. Write your
solution to prepend below.
3. (10 points) Define a Scheme procedure difference that takes lists lst1 and
lst2 as arguments and that returns a new list obtained by removing all
values that appear in lst2 from lst1, otherwise preserving order. We saw
that Ruby provides this as a basic operation on Array objects (lst1 - lst2).
For example:
> (difference '(a 1 3 b (a 2) 2 c 19 8 2 b 3) '(a 2))
(1 3 b (a 2) c 19 8 b 3)
Your procedure should not change either of the lists passed as parameters.
Write your solution to difference below.
4. (10 points) Define a Scheme procedure prefix that takes two lists as
arguments and that returns #t if the first list is a prefix of the second
and that returns #f otherwise. The first list is considered a prefix of the
second if its elements appear at the front of the second list in the same
order. The values in the lists might be of any type, not just numbers.
For example:
> (prefix '(1 8 3) '(1 8 3 17 95))
#t
> (prefix '(a b c) '(a b c d e f))
#t
> (prefix '(3 9 12) '(3 9 a b c))
#f
> (prefix '(3 9 12) '(3 9))
#f
By definition, the empty list is considered a prefix of any other list and a
list is considered a prefix of itself. Your procedure should not change
either of the lists passed as parameters. Write your solution to prefix
below.
5. (10 points) Define a Scheme procedure multiples that takes as an argument a
list of integers and that returns a new list that indicates a count of the
number of multiples each value has in the original list. For example:
> (multiples '(9 8 1 2 3 16))
(1 2 6 3 2 1)
The value 9 is replaced by 1 because only 1 value in the original list is a
multiple of 9 (9 itself). The value 8 is replaced by 2 because there are 2
multiples of 8 (8 and 16). The value 1 is replaced by 6 because there are 6
multiples of 1 (all 6 numbers). The value 2 is replaced by 3 because there
are 3 multiples of 2 (8, 2 and 16). And so on. Assume that all values in
the list are integers greater than 0. Your procedure should not change the
list passed as a parameter. Write your solution to multiples below.
6. (10 points) Define a Scheme procedure choose that takes an integer n and a
list of values as arguments and that returns a new list that includes all
lists that can be formed by choosing n values from the original list in
order. For example:
> (choose 2 '(1 2 3 4 5))
((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5))
This list includes all possible ways to choose 2 values from the numbers 1
through 5. Notice that values are chosen in the same order in which they
appear in the original list. You may assume that there are no duplicates in
the original list and you may list the solutions in any order. For example,
(1 2) is a solution while (2 1) is not (because the order has to match the
order in the original list), but the solution (1 2) does not have to appear
before the solution (1 3) in the answer, which means that the solution given
above is just one possible right answer.
Your procedure should work for lists of any type, as in:
> (choose 0 '(a b c))
(())
> (choose 1 '(a b c))
((a) (b) (c))
> (choose 2 '(a b c))
((a b) (a c) (b c))
> (choose 3 '(a b c))
((a b c))
> (choose 4 '(a b c))
()
Notice that there is exactly one way to choose 0 values from a list (the
empty list) and that there are no ways to choose n values from a list of
length less than n.
Your procedure should call the error procedure if the integer is less than
0. Your solution has to avoid gross inefficiency. For example, it can't
require time greater than O(m^n) where m is the length of the list and n is
the number of items to choose. Your procedure should not change the list
passed as a parameter. Write your solution to choose below.
7. (8 points) Assuming that the following variables have been defined:
x = [3, 8, 9, 7, 4, 5]
y = 2..4
sum = 0
(2 points) Part A: What output is produced by the following code?
x.each {|n| puts 2 * n - 1}
(2 points) Part B: What output is produced by the following code?
y.each {|n| puts n * x[n]}
(2 points) Part C: What output is produced by the following code?
sum = 0
y.each do |n|
sum += n
puts n
end
puts sum
(2 points) Part D: What value is returned by the following expression?
x.map {|n| [n, n]}
8. (8 points) Define a Ruby method match(lst1, lst2) that takes two arrays as
arguments and that returns an array containing the values in order from the
two arrays that match. A value is considered to be a match if it appears in
both arrays in the same position. For example:
>> match([3, 8, 19, 7, 4], [19, 8, 4, 7, 4, 12, 13])
=> [8, 7, 4]
>> match(["t", "e", "m", "p", "l", "e"], ["t", "a", "m", "p", "e", "r"])
=> ["t", "m", "p"]
Notice that one array can be longer than the other. Your method should not
change either of the arrays that are passed as parameters. Write your
solution to match below.
9. (8 points) Define a Ruby method unique(lst) that takes an array as an
argument and that returns a new array containing the values from lst minus
any duplicates. The new array should have the values in the same relative
order as their first occurrence in the original array. In other words, a
value i should appear before a value j in the result if and only if the
first occurrence of i appears before the first occurrence of j in the
original array. For example:
>> unique([14, 8, 12, 1, 11, 10, 4, 9, 1, 2, 5, 2, 4, 12, 12])
=> [14, 8, 12, 1, 11, 10, 4, 9, 2, 5]
>> unique(["m", "i", "s", "s", "i", "s", "s", "i", "p", "p", "i"])
=> ["m", "i", "s", "p"]
This is such a useful operation that Ruby includes it in the Array class as
a method called uniq with a mutator uniq!. You may not call these built-in
versions to solve the problem. Your method should not change the array
passed as a parameter. Write your solution to unique below.
10. (8 points) Define a Ruby method split(lst,n) that takes an array lst and an
integer n as arguments and that returns an array of n arrays containing the
values from the original array. The first n values from the original array
should become the first values, in order, in the n arrays of the new array.
The second set of n values from the original array should become the second
values, in order, in the n arrays of the new array. And so on. For
example:
>> split([3, 4, 5, 6, 10, 13, 4, 9, 8], 3)
=> [[3, 6, 4], [4, 10, 9], [5, 13, 8]]
Notice that the first 3 values (3, 4, 5) are the first values in the
three arrays in the result and they appear in order (3 is included in the
first array, 4 is included in the second array, 5 is included in the third
array). Similarly, the second group of 3 values (6, 10, 13) are the second
values of the three arrays, also in order (6 in the first array, 10 in the
second, 13 in the third). If the last group of numbers does not have n
values, then your method should add as many values as it can to the
appropriate arrays. For example:
>> split([3, 4, 5, 6, 10, 13, 4, 9, 8, 7], 4)
=> [[3, 10, 8], [4, 13, 7], [5, 4], [6, 9]]
The final group of values has just two values (8, 7), so only the first two
of the arrays in the result have a third value. It is possible to get an
empty array in the result, as in:
>> split(["hello", "world", "today"], 5)
=> [["hello"], ["world"], ["today"], [], []]
You may assume that the integer passed to your method is greater than 0.
Your method should not change the array passed as a parameter. Write your
solution to split below.
11. (8 points). Extend the Array class to have a new method called values that
generates pairs of values that each have a value from the array and the
number of occurrences of that value. Each different value from the array
should be generated just once and should be generated in the order in which
it appears in the array. A client would use a block with two parameters to
access the pairs generated by your method. This code, for example:
x = [9, 7, 9, 5, 0, 6, 5, 12, 5, 9, 11, 2, 3, 0, 0, 9, 3, 10, 3, 6]
x.values {|v, count| print v, " occurs ", count, " times\n"}
should produce the following output:
9 occurs 4 times
7 occurs 1 times
5 occurs 3 times
0 occurs 3 times
6 occurs 2 times
12 occurs 1 times
11 occurs 1 times
2 occurs 1 times
3 occurs 3 times
10 occurs 1 times
Your method should return the number of values generated (10 in the example
above). Your method should not change the array. Write your solution to
values below.
]]>