Description

Paul Vrbik
In addition to this written work there are four coding questions. The written work is worth 35 points and the coding questions are worth 60 points totalling 95 points.
Tail Recursion
The mean of a collection of observations x1, x2, . . . , xn is given by
1 n
x¯n = ∑ xk.
n k=1
At first glance it does not seem that x¯n+1 is related to x¯n but notice
1 n+1 1 n ! 1
x¯n+1 = ∑ xk = xn+1+ ∑ xk = (xn+1+ n x¯n) n + 1 k=1 n + 1 k=1 n + 1
and thereby
x¯n+1 = xn+1+ n x¯n.
n + 1
We have shown how to compute x iteratively¯ . In particular we compute x¯n+1 from only (n, x¯n, xn+1).
Question 1. [2marks]
The definition of variance (specifically sample variance) of a collection of observations x1, x2, . . . , xn is
Sn2 = ∑(xk − x¯n)2.
n k=1
Take for granted (though it is easy to show) that (1)
1 n
S (2)
and use (1) and (2) to derive an iterative definition for variance. That is, produce an equation which computes Sn2+1 from only (n, Sn2, x¯n, x¯n+1, xn+1).
Question 2. [2marks]
Define a linear recursive
lcVariance :: [Float] -> Float
that computes the variance Sn2 of a list. Your function must use lcVariance xs to compute lcVariance (x:xs). Note, fromIntegral.length is compatible with Float.
Question 3. [4marks]
Define a tail recursive helper function with type:
trVariance :: Float -> Float -> Float -> [Float] -> Float
that finds the variance of the list.
1. a call to itself with different inputs, or
2. one of the inputs.
Question 4. [1mark]
Define
variance :: [Float] -> Float
via a single call to trVariance.
Question 5. [1mark]
Define an iteration invariant for trVariance that proves the correctness of variance.
Question 6. [5marks]
Prove trVariance satisfies your iteration invariant.
Question 7. [1mark]
State the bound value for trVariance.
Question 8. [2marks]
Prove your bound value is always non-negative and decreasing.
Question 9. [2marks]
Define two distinct quick-checks for variance that both use lists from Arbitrary [Float].
In particular, your quick-checks should be for lists of arbitrary length.
Induction
Consider the following definitions for implementing addition on natural numbers.
1 data Nat = Zero | Succ Nat deriving Show
2 plus :: Nat -> Nat -> Nat
3 plus m Zero = m
4 plus m (Succ(n)) = Succ (plus m n)
Question 10. [7marks]
Using induction prove:
plus Zero n = n
for any n :: Nat.
Question 11. [8marks]
Using induction prove that plus is commutative, that is,
plus m n = plus n m
for any n,m :: Nat.
Hint: Keep m fixed and do induction over n.
Note: There are style marks for this question so be sure to justify each of your lines and include all necessary components of induction.