Assignment 1 - Hints for the Bonus Challenge

Can you give us some hints for the Bonus Challenge ?
An example may help to clarify the issues. Suppose the input is
```
[1 0 0 1 0 2]
```
The parameters a, b and c must be chosen to minimize this function:
E = (0 - (b + c))² + (1 - c)² + (0 - (a + c))² + (2 - (b + c))²
The minimum of this function (which is quadratic and positive definite) will occur at the place where the derivatives of E with respect to a, b and c are zero. These derivatives are:
```
dE
-- = 2(a + c)
da

dE
-- = 2(b + c) - 2(2 - (b + c)) = 4(b + c - 1)
db

dE
-- = 2(b + c) - 2(1 - c) + 2(a + c) - 2(2 - (b + c)) = 2(a + 2b + 4c - 3)
dc
```
Solving these equations simultaneously gives a=-1, b=0, c=1;
so new items in the sequence will be predicted according to the equation
u_k = au_k-1 + bu_k-2 + c = -u_k-1 + 1
The output is therefore
```
[-1 2 -1 2 -1]
```
In general, we have
E = Σ_1<k<n [ u_k - (au_k-1 + bu_k-2 + c)]²
So the derivatives are:
d_aE = Σ_1<k<n -2u_k-1[ u_k - (au_k-1 + bu_k-2 + c)] = 2[-Σu_k-1u_k + Σu_k-1²a + Σu_k-1u_k-2b + Σu_k-1c]
d_bE = Σ_1<k<n -2u_k-2[ u_k - (au_k-1 + bu_k-2 + c)] = 2[-Σu_k-2u_k + Σu_k-2u_k-1a + Σu_k-2²b + Σu_k-2c]
d_cE = Σ_1<k<n -2[ u_k - (au_k-1 + bu_k-2 + c)] = 2[-Σu_k + Σu_k-1a + Σu_k-2b + (n-2)c]

This gives three simultaneous equations, whose coefficients can be updated for each new item in the sequence. Solve them simultaneously and you will obtain a,b,c.
Do we need to worry about roundoff errors, etc, for the Bonus Challenge ?
For the Bonus Challenge, the automarking script will try to avoid using any data that could cause a division by zero, so it shouldn't be a problem.
Are we required to use only "constant space" ?
Although this is possible, it is not required; i.e. you are welcome to use an array or ArrayList, etc, if you like; and you may assume there will be no more than 128 items in the input.

Back to Assignment 1 | Back to the main page