download stub
download solution
- 4 Points: Consider the problem of finding the maximum value in a binary tree.
One way to do this is to write a generic fold function for binary
trees, as well as a max function that takes three args. The fold
function should fold some function f over the binary tree such
that a tree with subtrees left and right, and value
v at the root gives the result f(fold(left),v,fold(right).
Since left or right, or both might be empty trees,
we need some value corresponding to fold(empty). Thus, our
function definition looks like this:
fun fold (f:'b*'a*'b->'b) (empty_value:'b) (t:'a tree):'b = ...Where empty_value is the value used in place of fold(empty). Once fold is implemented properly, we can do:fun max(a:int,b:int,c:int):int = ... fold max 0 treeThis will find the maximum value in the tree, using 0 as the maximum value for the empty tree (so, if all values are negative, the result will be 0). In addition to implementing fold so it works with the max function, you should also use fold to build a string that lists the values of all the nodes in an int tree by writing a function concat3:string*int*string->string. - 6 Points:
Another type of fold uses an inorder traversal of a binary
tree, which is a way of enumerating all of the nodes in the tree.
First, the left subtree is enumerated, then the root node, and then
the right subtree. Naturally, this process is done recursively on the
subtrees. We can define inorder fold analogously to the way
foldl and foldr are defined for lists. That is, a fold on the
elements of the tree done using an inorder traversal. For instance,
consider the tree shown below. An inorder traversal is 4-2-1-5-3-6.
You should write two functions: inorderFoldl and inorderFoldr. For
the following tree,
fun concat (a:int,b:string) = b^Int.toString(a) (* inorderFoldl f b tree = f(6,f(3,f(5,f(1,f(2,f(4,b)))))) *) inorderFoldl concat "" tree = "421536" inorderFoldr concat "" tree = "635124"
download stub
download solution
Given a list of integers, a subsequence of that list is a list formed by removing 0 or more elements from the original list. Thus, [3,5,7] is a subsequence of [1,3,6,5,7]. An increasing subsequence is a subsequence where each element in the subsequence is strictly less than the next element in the subsequence. Thus, [3,5,7] is an increasing subsequence of [1,3,6,5,7], while [6,5] is a subsequence, but is not increasing. A longest increasing subsequence (LIS) of a list is the increasing subsequence with the most elements. Thus, [1,3,5,7] is a LIS of [1,3,6,5,7]. Note that the LIS of a list is not unique, as [1,3,6,7] is a LIS also, though they naturally have the same length.
The typical way to find a LIS of a list uses a technique called dynamic programming. First, a bit of notation: assume there are N elements in the list, and element i of the list is xi. For each 1≤i≤N, we can compute the LIS that ends with xi. For instance, if i = 3 for the above sequence, we find that the LIS ending with xi is [1,3,6]. We will denote the LIS ending with xi as Li. Notice that the LIS for the whole list is the longest of the Li's, since some element must be the last element of the LIS of the whole sequence. So, if we could just figure out a good way to compute each Li, we would have our answer.
With a little bit of thought, we can see that Li is either of the form Lj@[xi], for some 0<j<i, or is of the form [xi]. Thus, to find Li, we need to try to append xi to each Lj, where xi > xj. This allows us to efficiently compute Li, since we can compute Li after computing each Lj where j < i.
Your task is to write a function LIS:(int list)->(int list) that computes a longest increasing subsequence of its input. Make sure that your program is efficient and does not compute any Li more than once. Your program should be able to quickly compute a LIS for lists with hundreds of elements. Here are a few examples (note that the outputs may not be unique, and your function just needs to return any one of the possibly many LIS's):
LIS([1,2,3,4]) = [1,2,3,4]
LIS([4,3,2,1]) = [3]
LIS([1,2,2,2]) = [1,2]
LIS([5,2,7,8,3,2,5,7,8,3]) = [2,3,5,7,8]
In addition to your solution (which can be implemented in under 20
lines of code), you should include a comment analyzing the complexity
of your implemenation. Your complexity should be no worse than
O(N3), where N is the number of elements in the input to
LIS. You will receive 9/10 points for a correct implementation which
you correctly analyze as having a complexity of O(N3). A
better solution has complexity of only O(N2), which is
required to receive the full 10 points.
download stub
download solution
A simple way to generate a sequence of random numbers, x0, x1, ... is to set the first term, x0, to the seed, an input to the random number generator. Subsequent terms are then given by the recurrence:
xi = (xi-1*a+b) mod ca, b, and c are all constants and their selection plays an important role in the quality of the random number generator. After you get your number generator to work, you should experiment with it, and try to find good values for a, b, and c. In particular, try plotting xi vs i -- the result should show no obvious pattern.
Typically, when this type of generator is implemented, some state is maintained in memory between calls (the previous value of xi). However, in a functional programming style, we want to avoid any state. One way to deal with this is to construct a new function, as well as a random number, every time the random number generator is called. That way, a call do the random number generator produces not only a random number, but also a function to produce the next random number in the sequence. This is done by returning a pair of type rand. The first term of the pair is the next random number in the sequence. The second term is a function that takes no arguments, but when it is called it returns the next random number in the sequence, as well as a new function. To make all this work, we need to define a recursive data type:
datatype rand = Rand of (int*(unit->rand))Then, we can write a function to generate our random number generating function:
fun rand_gen(seed:int):unit->rand =
...
Once, you've implemented this function, you should be able to make a
list of random numbers as follows:
fun rand_list(seed:int,cnt:int):int list =
let val rg = rand_gen(seed)
fun go(f:unit->rand,cnt:int) =
if (cnt = 0) then []
else
let
val Rand(a,b) = f()
in
a::go(b,cnt-1)
end
in
go(rg,cnt)
end