<![CDATA[
CSE341 Sample Midterm handout #5
Unless otherwise noted, you may call any of the functions included on
the cheat sheet. You also may call any function that is included as a
problem on this exam, whether or not you correctly solve that problem.
You may call the utility functions described below that that we have discussed:
m--n
Returns a list of the sequential integers from m to n inclusive; returns an
empty list if m > n
reverse(list)
returns a list with the values from the given list in reverse order
explode(str)
returns a list of the characters of str
implode(list)
inverse of explode, converts a list of char values into a single string
map(f, list)
Returns the list obtained by applying f to every value of the given list
filter(f, list)
Returns a list of the values from the given list for which f(a) is true
reduce(f, list)
For a list [x1, x2, x3, ..., xn], returns x1 for a list of length 1,
otherwise returns f(x1, f(x2, f(x3, ..., f(xn-1, xn)...)))
qsort(f, list)
Returns the result of sorting the given list using the given comparison
function where f(a, b) indicates that a < b (runs in O(n log n) time)
curry(f)
converts ('a * 'b -> 'c) into 'a -> 'b -> 'c
uncurry(f)
converts 'a -> 'b -> 'c into ('a * 'b -> 'c)
infix operator %
function composition, as in f % g(n) = f(g(n))
Unless otherwise specified, you can write your own helper functions, but you
are not allowed to use library functions not listed on the cheat sheet.
1. OCaml Expressions, 20 points. For each OCaml expression in the left-hand
column of the table below, indicate in the right-hand column its value. Be
sure to put any string value inside double-quotations marks ("hello" vs
hello). Assume that the following value has been declared:
let words = ["live"; "long"; "and"; "prosper"]
Expression Value
-------------------------------------------------------------------------------
reduce(uncurry( * ), 3--5) _______________________________
map(List.hd % List.tl,
[8--12; 4--9; 7--8; 8--10]) _______________________________
map((fun x -> x mod 4), 1--7) _______________________________
reduce(uncurry(+),
map((fun x -> x * x), 1--4)) _______________________________
filter((fun x -> x mod 4 > 1), 1--12) _______________________________
map((fun x -> "(" ^ x ^ ")"), words) _______________________________
reduce(uncurry(@), [1--3; 4--6; 5--7]) _______________________________
map((fun x -> float_of_int(x) +. 0.5), 1--4) _______________________________
reduce(uncurry(+), map(String.length, words)) _______________________________
reduce(uncurry( * ),
map((fun x -> 2 * x - 1), 2--4)) _______________________________
2. OCaml Types, 10 points. For each OCaml expression in the left-hand column
of the table below, indicate its type in the right-hand column assuming the
expression was added to the standard top-level environment. Assume that the
following value has been declared:
let lst = [("foo", 3); ("bar", 2); ("baz", 19)]
Expression Type
-------------------------------------------------------------------------------
lst _______________________________
[List.tl(lst)] _______________________________
(8, [["a"; "b"]; ["c"; "d"]]) _______________________________
fun x -> (List.hd(x) mod 3, List.tl(x)) _______________________________
float_of_int % List.hd % List.tl _______________________________
3. Scope, 5 points. What value is answer bound to after executing the
following code?
let y = 10
let z = 20
let f(n, z) =
let x = 4 + y
in let y =
let x = 2
in let z = 3
in n + x + z
in x + y + n + z
let answer = f(40, 100)
4. Curried functions, 10 points. For this problem, in addition to being able
to call the functions listed on the front page of the test, you may call the
curried versions of map, filter and reduce described below.
fun map2 f list
curried version of map
fun filter2 f list
curried version of filter
fun reduce2 f list
curried version of reduce
The following problems must be solved as one-line let bindings using curried
functions, standard operators, function composition, and map2, filter2, and
reduce2. Remember that the percent sign is our function composition
operator, as in f % g which returns a function that computes f(g(n)).
(4 points) Define a function sum_positives that takes a list of integers as
an argument and that returns the sum of the positive values in the list.
(6 points) Define a function strip that takes a list of nonempty strings as
an argument and that returns the list obtained by stripping the last
character from each string. For example:
strip(["hello"; "there"; "old"; "pal"]) should return
["hell"; "ther"; "ol"; "pa"]
5. Functions, 6 points. Write a function powers(n, m) that takes integer
arguments n and m and that returns a list of the powers of m from 0 to n
inclusive. For example, powers(5, 2) should return [1; 2; 4; 8; 16; 32]
(which is 2^0, 2^1, ..., up to 2^5). Your function must run in O(n) time,
which means that it should require approximately n multiplications. You may
assume that n is not negative.
6. Functions, 6 points. Write a function sorted_chars that takes a string s as
an argument and that returns the string composed of the sorted lowercase
version of the alphabetic characters from s. For example,
sorted_chars("Stuart Reges??") should return "aeegrrssttu". This function
would be useful for finding anagrams. For example, if you make the call
sorted_chars("Sugar--Street"), you get the same result, indicating that
these two strings are anagrams. In writing your function, you may call
is_alpha to test whether a character is a letter and Char.lowercase_ascii to
convert a letter to lowercase.
7. Functions, 11 points. Write a function interleave that takes two lists as
arguments and that returns the list obtained by combining elements from the
two lists in an alternating fashion. The first pair of values in the result
should be the first values of the two lists. The second pair of values in
the result should be the second values in the two lists. And so on. In
each pair, the first value should be from the first list passed as a
parameter and the second value should be from the second list passed as a
parameter. For example, interleave([1; 2; 3], [10; 20; 30]) should return
[1; 10; 2; 20; 3; 30] while interleave([10; 20; 30], [1; 2; 3]) should
return [10; 1; 20; 2; 30; 3]. If one list has more values than the other,
then those values should be appended after the interleaved pairs. For
example, interleave([1; 2], [10; 20; 30; 40; 50]) should return [1; 10; 2;
20; 30; 40; 50] while interleave([1; 2; 3; 4; 5], [10; 20]) should return
[1; 10; 2; 20; 3; 4; 5].
8. Types, 11 points. Recall the type we discussed in lecture for storing a
binary tree of integers:
type int_tree = Empty | Node of int * int_tree * int_tree
(4 points) Write a function nodes that takes an int_tree as a parameter and
that returns a count of the number of nodes in the tree.
(7 points) Write a function leaves that takes an int_tree as a parameter and
that returns a list of the data values stored in leaf nodes of the tree.
The leaf values should be listed from left to right (i.e., in the same order
in which they would be visited by any standard tree traversal).
9. Functions, 11 points.
(8 points) Write a function cartesian_product that takes two lists as
arguments and that returns a list that contains each of the ordered pairs
(x, y) where x is an element of the first list and y is an element of the
second list. The pairs can appear in any order in the result. For example:
cartesian_product([1; 2; 3], ["a"; "b"]) could return
[(1, "a"); (1, "b"); (2, "a"); (2, "b"); (3, "a"); (3, "b")] or could
return [(1, "a"); (2, "a"); (3, "a"); (1, "b"); (2, "b"); (3, "b")]
These are only two possible answers because the pairs can be listed in any
order in the result. If either list passed as a parameter is empty, the
result should be an empty list. Your function should run in O(m * n) time
where m and n are the lengths of the two lists.
(3 points) Write a function product that takes two lists of integers as
arguments and that returns the list of all possible products formed by
multiplying a value from the first list by a value in the second list. You
may assume that the lists contain no duplicates. The values may appear in
any order in the result. For example, the call product([1; 2; 3], [5; 7])
should return a list of the 6 possible values obtained by multiplying one of
the 3 numbers in the first list by one of the 2 numbers in the second list.
One possible answer is [5; 7; 10; 14; 15; 21]. You should use
cartesian_product to write your solution. As with cartesian_product, if
either list passed as a parameter is empty, the result should be an empty
list.
10. Functions, 10 points. Write a function factors that takes the prime
factorization of an integer as an argument and that returns a list of all
of its factors. Recall that a factor of an integer is a number that goes
evenly into it. For example, the factors of 24 are [1; 2; 3; 4; 6; 8; 12;
24]. Your function will be passed a list of tuples of the form (p, n)
where each tuple indicates that the number has a factor of p to the nth
power where p is a prime. For example, the prime factorization of 24 is
2^3 * 3^1, so it would be represented as [(2, 3); (3, 1)]. The factors can
appear in any order. For example:
factors([(2, 3); (3, 1)]) could return [1; 2; 3; 4; 6; 8; 12; 24]
or it could return [1; 3; 2; 6; 4; 12; 8; 24]
Because the factors can appear in any order, these represent just two of
the possible correct answers. As another example, if we wanted to compute
the factors of 600, we would make this call:
factors([(2, 3); (3, 1); (5, 2)])
One possible answer is:
[1; 5; 25; 3; 15; 75; 2; 10; 50; 6; 30; 150; 4; 20; 100; 12; 60; 300;
8; 40; 200; 24; 120; 600]
Your function must use the prime factorization to solve this problem. You
can't, for example, search for factors by checking consecutive integers.
Another way of saying this is that the running time of your function has to
be related to the number of factors rather than the magnitude of the
factors.
]]>