Homework 1 Sequence of real numbers

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
µ = (
i=n X i=1
xi)/n.
The variance is defined by the formula
ν = (
i=n X 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(nlogn). 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.