<![CDATA[
CSE431 Sample Final handout #7
For Scheme questions, you are not allowed to use mutating functions, you are
not allowed to use vectors, and in terms of functions that take lists as an
argument, you are limited to the following:
basic: length, car, cdr, cons, append, list, member, remove, assoc, reverse
positional: cadr, caddr, cadddr, cddr, cdddr, first, second, third
higher-order: map, filter, foldl, foldr, sort, andmap, ormap
predicates: null?, pair?, list?
Some problems may have additional constraints. For Ruby problems, unless
otherwise noted, you can use all of standard Ruby, but you can't use operations
that require loading specialized libraries.
For both Scheme and Ruby questions, you may define helper functions/methods,
although the helper functions in Scheme must be localized to the function so
that they do not become part of the top-level environment. For the Scheme
questions, you may call any Scheme function 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. If an expression produces an error
when evaluated, write "error" as your answer.
(2 points) Part A:
(define a 101)
(define b 103)
(define c 105)
(let ((c (+ a c))
(a (+ b c)))
(list a b c))
(2 points) Part B:
(define a 101)
(define b 103)
(define c 105)
(let* ((b (+ a b))
(a (+ b c)))
(list a b c))
(2 points) 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)
(4 points) 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))
2. (5 points) Define a Scheme function called occurrences that takes a value
and a list as arguments and that returns the number of occurrences of the
value in the list. Your function should use a deep equality comparison,
although it should not search for embedded occurrences (those inside a
sublist). You may assume that the second argument is a list. For example:
> (occurrences 3 '(7 9 2 4 a (3 2) 3 "hello" 3))
2
> (occurrences 'a '(3 a b a 19 (a b) c a))
3
> (occurrences '(a b) '(a b c (a b) d 3 a b (a b) 7))
2
> (occurrences 2 '(1 (2 3) 4 5 (2 2 2)))
0
3. (5 points) Define a Scheme function called remove-all that takes a value and
a list as arguments and that returns the result of removing all occurrences
of the value from the list. Your function should use a deep equality
comparison, although it should not remove embedded occurrences (those inside
a sublist). For example:
> (remove-all 2 '(1 2 3 4 2 7 2 (1 2 2) (3 (2 4) 2)))
'(1 3 4 7 (1 2 2) (3 (2 4) 2))
> (remove-all 'a '(a b c (a b) a (c) a a))
'(b c (a b) (c))
> (remove-all '(a 1) '(13 (a 1) 7 a 1 (a 1) 4 a 1))
'(13 7 a 1 4 a 1)
> (remove-all 2 '(1 3 3 4 (2 2 2) 7 (2 1 2)))
'(1 3 3 4 (2 2 2) 7 (2 1 2))
Your function must run in O(n) time where n is the length of the list. You
are not allowed to use the standard function called remove.
4. (10 points) Define a Scheme function called maximum that takes a list of
numbers as an argument and that returns the largest value in the list.
For example:
> (maximum '(1 13 -408 273 17 304 8 9))
304
> (maximum '(7.4 28 13.9 3.14159 2.71828 42))
42
You may assume that the value you are passed is a list and that it contains
only numbers. Your function should call the error procedure with the
message "max of empty list" if passed an empty list:
> (maximum '())
. . max of empty list
Your function must be efficient in several respects. It should be
tail-recursive, it should run in O(n) time where n is the length of the
list, and it should check the error condition only once. You are not
allowed to call the standard function called max in solving this problem.
5. (10 points) Define a Scheme function called pattern that returns a new value
that represents the kind of data passed to it. Numbers, strings, symbols,
and booleans should be converted into the symbols number, string, symbol,
and boolean, respectively. For example:
> (pattern 13)
'number
> (pattern 13.4)
'number
> (pattern "hello")
'string
> (pattern 'a)
'symbol
> (pattern #t)
'boolean
A list of values should be converted into the list of patterns for each
value in the list, as in:
> (pattern '(13 13.4 "hello" a #t))
'(number number string symbol boolean)
This conversion should occur at all levels of a list, preserving the list
structure:
> (pattern '(13 (13.4 "hello" (a #t)) (14 (a b))))
'(number (number string (symbol boolean)) (number (symbol symbol)))
> (pattern '((((17)))))
'((((number))))
Values that are not of one of these types (e.g., dotted pairs) should be
included without modification in the result:
> (pattern '(3 (3 . 4) a "hello" (a . b)))
'(number (3 . 4) symbol string (a . b))
Remember that Scheme has a series of predicates for testing whether data is
of a certain type (number?, string?, symbol?, boolean?, list?).
6. (10 points) Define a Scheme function called switch-pairs that takes a list
as an argument and that returns the list obtained by switching successive
pairs of values in the list. For example:
> (switch-pairs '())
'()
> (switch-pairs '(a b))
'(b a)
> (switch-pairs '(a b c d e f))
'(b a d c f e)
> (switch-pairs '(3 a (4 5) (6 7) 9 (1 2 3)))
'(a 3 (6 7) (4 5) (1 2 3) 9)
If the list has an odd number of values, then the final element should not
be moved. For example:
> (switch-pairs '(a))
'(a)
> (switch-pairs '(a b 3 (4 5) 9))
'(b a (4 5) 3 9)
Your function should call the error procedure with the message "not a list"
if passed something other than a list:
> (switch-pairs 3)
. . not a list
Your function must run in O(n) time where n is the length of the list.
7. (10 points) Define a Scheme function called overlap that takes two sorted
lists of numbers as arguments and that returns a list of the values in
common between the two lists. For example:
> (overlap '(1 2 2 3 3 4 7 7 7) '(1 2 2 2 2 3 5 7 8))
'(1 2 2 3 7)
You may assume that your function is passed two lists, that they contain
only numbers, and that the numbers appear in sorted (nondecreasing) order.
But as in the example above, they might contain duplicates. Any given
number from a list can match at most once. Thus, the two occurrences of 2
in the first list can match 2 of the occurrences of 2 in the second list,
but the additional occurrences of 2 in the second list do not appear in the
result because they aren't matched. Similarly, the result includes only one
7 even though the first list has three occurrences of 7 because the second
list has only 1 such occurrence.
Your function must take advantage of the fact that the lists are sorted. In
particular, your function has to run in O(n + m) time where n is the length
of the first list and m is the length of the second list.
8. (10 points) Define a Scheme function called histogram that takes a list of
values as an argument and that returns a list of 2-element lists where each
2-element list contains a value from the original list followed by a count
of that value in the original list. Each value from the original list
should produce exactly once such pair and they should appear in the order in
which the values first appear in the original list. For example:
> (histogram '(1 3 2 5 1 3 3 3))
'((1 2) (3 4) (2 1) (5 1))
The result indicates that the value 1 appeared twice in the original list,
the value 3 appeared 4 times, the value 2 appeared 1 time, and the value 5
appeared 1 time.
You may assume that your function is passed a list, but the list will not
necessarily contain simple values like numbers:
> (histogram '(a b c (a b) c (a b) b c a (a b)))
'((a 2) (b 2) (c 3) ((a b) 3))
9. (4 points) Assuming that the following variables have been defined:
x = 10..14
y = [2, 3, 5, 7, 11]
(1 point) Part A: What output is produced by the following code?
x.each {|n| puts n + 2}
(1 point) Part B: What output is produced by the following code?
for n in y do
puts n * 3
end
(2 points) Part C: What value is returned by the following expression?
x.map {|n| n % 2 == 0}
10. (6 points) Define a Ruby method called switch_pairs that takes an array as
an argument and that returns a new array that contains the same values with
successive pairs of values switched in order. For example:
>> switch_pairs([])
=> []
>> switch_pairs(["a", "b"])
=> ["b", "a"]
>> switch_pairs([1, 2, 3, 4, "a", "b", [3, 4], [5, 6]])
=> [2, 1, 4, 3, "b", "a", [5, 6], [3, 4]]
If the array has an odd number of values, then the final element should not
be moved. For example:
>> switch_pairs(["a"])
=> ["a"]
>> switch_pairs(["a", "b", 3, [4, 5], 9])
=> ["b", "a", [4, 5], 3, 9]
You may assume that your method is passed an array as a parameter. Your
method should not change the array that is passed as a parameter.
11. (6 points). Extend the Ruby Range class to have a new method called first
that takes an integer parameter n and that generates the first n values of
the range (i.e., that expects a block of code to be executed for the first
n values of the range). For example:
>> x = 1..10
=> 1..10
>> x.first(3) {|n| puts 2 * n + 1}
3
5
7
The method should use a default value of 1 for the parameter:
>> y = 10..20
=> 10..20
>> y.first {|n| puts n}
=> 10
You may assume that any value passed to the method is an integer. If the
value passed is less than 1, the method should not generate any values. If
the value passed is greater than the number of values in the range, you
should generate just the numbers in the range. You are not allowed to
construct an array in solving this problem. Don't worry about the fact
that this method overrides the predefined method called first.
12. (6 points). Extend the Ruby Array class to have a new method called
pairwise that uses a block to specify a 2-argument predicate, returning
true if the predicate is true of each adjacent pair of values in the array
and returning false otherwise. For example, we can use this method to test
whether an array is sorted as follows:
>> [3, 18, 24, 24, 42, 50, 75].pairwise {|x, y| x <= y}
=> true
The method compares the first adjacent pair (3, 18) to make sure that the
predicate is true, then compares the second adjacent pair (18, 24) to make
sure that the predicate is true, then compares the third adjacent pair (24,
24), and so on, until it compares the final adjacent pair (50, 75).
Below is an example of a predicate that tests whether a list is composed of
consecutive values.
>> [3, 18, 24, 24, 42, 50, 75].pairwise {|x, y| x + 1 == y}
=> false
>> [3, 4, 5, 6, 7, 8].pairwise {|x, y| x + 1 == y}
=> true
The method should return false if any pair fails the test, as in:
>> [3, 4, 5, 6, 7, 8, 10].pairwise {|x, y| x + 1 == y}
=> false
In this case, the only adjacent pair that fails is (8, 10). The method
should return true if there are no adjacent pairs to compare.
Your method should run in O(n) time where n is the length of the array and
should stop checking as soon as it finds a pair that fails. Your method
should not change the original array.
13. (8 points). Extend the Ruby Array class to have a new method called
mode that returns the most commonly occurring element in a sequence of
values (statisticians refer to this value as the mode). Assume that values
are arranged so that duplicates appear next to each other in the array.
Your method should return an array of length 2 that contains the mode
followed by the number of occurrences of the mode. For example:
>> [1, 8, 8, 8, 10, 14, 14, 25, 25].mode
=> [8, 3]
This result indicates that 8 occurred most frequently and that it occurred
3 times. If there is a tie, your method should return the first value:
>> [1, 8, 8, 8, 10, 14, 14, 14, 25, 25, 25].mode
=> [8, 3]
Three different values occurred 3 times (8, 14, and 25), but the method
returned the first one. The values might not be simple numbers:
>> [1, 1, 1, "foo", "bar", "bar", "bar", "bar", [7, 8]].mode
=> ["bar", 4]
>> [[1, 2], [1, 2], [1, 2], 7, 7, "foo", "foo"].mode
=> [[1, 2], 3]
The method should return nil and 0 occurrences if called on an empty array:
>> [].mode
=> [nil, 0]
Your method must run in O(n) time where n is the length of the array. As
noted above you should assume that duplicate values are grouped right next
to each other in the array. Your method should not change the array.
]]>