<![CDATA[
CSE413 Sample Midterm handout #3
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 numbers = [3; 4; 9]
Expression Value
-------------------------------------------------------------------------------
reduce(uncurry(+), numbers) _______________________________
map((fun x -> x--(x+1)), numbers) _______________________________
map(List.length % List.tl,
[1--5; 3--5; 5--5; 2--5]) _______________________________
filter((fun x -> 24 mod x = 0), 1--7) _______________________________
reduce(uncurry( * ),
map((fun x -> x - 1), numbers)) _______________________________
map((fun x -> (x, x)), numbers) _______________________________
reduce(uncurry(+),
map((fun x -> 2 * x - 1), 1--5)) _______________________________
reduce(uncurry(@),
map((fun x -> [x; x]), numbers)) _______________________________
filter((fun x -> x/4 = 3), 1--15) _______________________________
implode(map(List.hd % reverse % explode,
["foo"; "bar"; "baz"])) _______________________________
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 = ["to"; "be"; "or"; "not"; "to"; "be"]
Expression Type
-------------------------------------------------------------------------------
lst _______________________________
(lst, lst) _______________________________
[lst; lst] _______________________________
fun x -> (x, [[x + 1]; [x + 2]]) _______________________________
fun (x, y) -> [(x, 1); (2, y)] _______________________________
3. Scope, 5 points. What value is answer bound to after executing the
following code?
let x = 40
let y = 5
let z = 25
let f(x) =
let z =
let y = 2
in let x = 10
in x + y
in let y = x - 5
in let x = y - 5
in x + y + z
let answer = f(20)
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 product that takes a list of integers as an
argument and that returns the product of the nonzero values in the list.
For example, product([2; 0; 3; 0; 4]) should return 24. You may assume
there is at least one nonzero value in the list.
(6 points) Define a function star_string that takes a list of strings as an
argument and that returns a new string obtained by concatenating the
strings together with an asterisk in front of each. For example:
star_string(["one"]) should return "*one"
star_string(["foo"; "bar"; "baz"]) should return "*foo*bar*baz"
star_string(["a"; "b"; "c"; "d"]) should return "*a*b*c*d"
You may assume the list has at least one string.
5. Functions, 6 points. Write a function zip that takes two lists as arguments
and that returns the list obtained by combining pairs of values in
corresponding positions into tuples. The first tuple should contain the
first values from each list. The second tuple should contain the second
values from each list. And so on. If one list is shorter than the other,
then zip should return a list of that shorter length. For example:
zip([1; 2; 3], ["a"; "b"; "c"]) should return
[(1, "a"); (2, "b"); (3, "c")]
zip([1; 2; 3; 4; 5], ["a"; "b"; "c"; "d"]) should return
[(1; "a"), (2, "b"); (3, "c"); (4, "d")]
zip(["a"; "b"; "c"; "d"], [1; 2]) should return [("a", 1); ("b", 2)]
6. Functions, 6 points. Write a function digit_sum that takes an integer n as
an argument and that returns the sum of the digits of n. For example:
digit_sum(384) should return 15
digit_sum(333) should return 9
digit_sum(-71) should return 8
digit_sum(0) should return 0
digit_sum(208034239) should return 31
7. Functions, 11 points. Write a function max_size_sublist that takes a list
of strings and an integer n as arguments and that returns a list of n of
those strings whose sizes are maximal. In other words, the function is
picking the n elements of the list that have the greatest size. Any given
string can be used only once. Assume that the list contains no duplicates.
The list you return can be in any order and if there is more than one list
of maximal size, then you can return any one of them. For example:
max_size_sublist(["four"; "score"; "and"; "seven"; "years"; "ago"], 1)
could return ["seven"]
max_size_sublist(["four"; "score"; "and"; "seven"; "years"; "ago"], 3)
could return ["seven"; "score"; "years"]
max_size_sublist(["aaaa"; "b"; "cc"; "ddd"; "eeeee"], 3)
could return ["eeeee";"aaaa";"ddd"]
Recall that the function called String.length is used to find the length of
a string. You may assume that the parameter n is greater than or equal to 0
and that it is less than or equal to the length of the list.
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
(5 points) Write a function same_structure that takes two int_trees as
arguments and that returns whether or not the two trees have the same
structure (true if they do, false otherwise). Two trees are considered to
have the same structure if they have the same number of nodes in the same
relative positions (the data stored in the tree doesn't matter).
(6 points) Write a function at_level that takes an int_tree and an integer n
as arguments and that returns a list of the data values stored at level n in
the tree. The overall root is considered to be at level 1, its children are
at level 2, its grandchildren are at level 3, and so on. The 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). You may assume that n is greater
than or equal to 1.
9. Functions, 10 points. Write a function same_digit_sum that takes two lists
of integers and that returns a list of all (x, y) tuples where x is from the
first list, y is from the second list, both are in the same position in
their respective lists, and both have the same digit sum. For example:
same_digit_sum([13; 8; 72; 308], [202; 13; 308; 2020403]) should return
[(13, 202); (308, 2020403)]
The first pair of numbers has a digit sum of 4 and the second pair of
numbers has a digit sum of 11. Notice that we don't get (13, 13) as an
answer even though the number 13 appears in both lists. That match doesn't
appear because the two occurrences of 13 are in different positions in the
list. Also notice that the pairs should be listed in the order in which
they appear in the original lists.
Notice that one list can be shorter than the other. For example:
same_digit_sum([12; 42; 73], [111; 55; 82; 19; 201; 24]) should return
[(12, 111); (73, 82)]
10. Functions, 11 points. Write a function combine that takes a list of
integers and a minimum value n as arguments and that returns a list of
tuples formed by combining sequences of sequential values from the list so
that their sum is greater than or equal n. Your function should combine
values from the front of the list by adding them up until their sum is at
least n. Once you have a sum that is at least n, you should include a
tuple in the result that includes the count of values combined and the sum.
The function should then combine values again until it finds a sum that is
at least n and should include a count/sum tuple for that group of combined
values. It should continue combining values in this way until it reaches
the end of the list. For example:
combine([1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12], 10) should return
[(4, 10); (2, 11); (2, 15); (2, 19); (1, 11); (1, 12)]
This result indicates that the first 4 values from the list were combined
for a sum of 10 (the values 1, 2, 3, and 4), then 2 values were combined
for a sum of 11 (the values 5 and 6), then 2 values were combined for a sum
of 15 (the values 7 and 8), then 2 values were combined for a sum of 19
(the values 9 and 10), then 1 value was combined for a sum of 11 (the value
11), and finally 1 value was combined for a sum of 12 (the value 12).
It is possible that your function will run out of values to combine at the
end of the list, so that the final sum might not be greater than or equal
to n. That is okay. For example:
combine([3; 8; 7; 6; 12; 2; 4; 7; 2; 9; 5; 2], 11) should return
[(2, 11); (2, 13); (1, 12); (3, 13); (2, 11); (2, 7)]
Notice that the final tuple has a sum of 7, which is less than the 11
minimum we are trying to achieve. This should happen only for the last
sequence of numbers combined. You may assume that all of the numbers in
the list are positive. If there are no values to combine, your function
should return an empty list.
]]>