Description
Q1. 20 points In statistics it is common to compute the variance of a sequence of real numbers1
.
Given a sequence of (real) numbers x1, x2, . . . , xn the mean is defined to be the average
value, which is given by the formula
µ = (X
i=n
i=1
xi)/n.
The variance is defined by the formula
ν = (X
i=n
i=1
(xi − µ)
2
)/n
in words, the average of the squares of the differences between the given values and
the mean value. Write an SML program to compute the variance of a given list of real
numbers. You may assume that the list is not empty and you need not write error
handling code: you need to learn more about SML to do it nicely. On the web page
we have written a little of the code to start you off.
Q2. 20 points Implement in SML a function that tests whether an element is a member of a given
list. Here are examples of the function in action.
1This is a very special case of computing the variance of a random variable; you do not have to know the
general concept for this question.
1
– member(1,[1,2,3]);
val it = true : bool
– member(1,[]);
val it = false : bool
– member(1,[2,3,4]);
val it = false : bool
The type should be
val it = fn : ’’a * ’’a list -> bool
Implement a function remove that takes an element and a list and removes all copies
of the element from the list. If the element is not in the list the function should return
the same list.
Q3. 15 points Write a function isolate that takes a list and makes a list with only one copy of each
element of the original list. I do not care if the order is scrambled in the process.
val l5 = [1,2,3,1,2,4,5,6,3,7,8,5,…] : int list
– isolate l5;
val it = [1,2,3,4,5,6,7,8,9] : int list
Q4. 20 points Write a function common that takes a pair of lists and forms a new list containing a
unique copy of each element that occurs in both lists.
common(l1,l2);
val it = [4,5,6] : int list
– common(l1,l4);
val it = [2] : int list
– common(l4,l1);
val it = [2] : int list
– common(l2,l4);
val it = [] : int list
– common;
val it = fn : ’’a list * ’’a list -> ’’a list
Q5. 25 points The mergesort algorithm is a recursive algorithm for sorting lists which runs in time
O(n log n). The items in the list must have an order relation defined on them, otherwise
sorting does not make sense of coruse.
The idea is as follows: the given list l is split into two equal (if the length of l is odd
then one of the “halves” is one item longer than the other) lists l1 and l2. These lists
are sorted recursively and then the results are merged back to give a single sorted
list. Code this in Sml. Your algorithm can use < as a comparison operator. Your
code should have a function split that produces a pair of lists, a function merge that
merges sorted lists and a function mergesort that implements the overall algorithm.
2