# Assignment 1 - Hints for the Bonus Challenge

1. 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))2 + (1 - c)2 + (0 - (a + c))2 + (2 - (b + c))2 ```

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

uk = auk-1 + buk-2 + c = -uk-1 + 1

The output is therefore

```[-1 2 -1 2 -1]
```
In general, we have

E = Σ1<k<n [ uk - (auk-1 + buk-2 + c)]2

So the derivatives are:

daE = Σ1<k<n -2uk-1[ uk - (auk-1 + buk-2 + c)] = 2[-Σuk-1uk + Σuk-12a + Σuk-1uk-2b + Σuk-1c]
dbE = Σ1<k<n -2uk-2[ uk - (auk-1 + buk-2 + c)] = 2[-Σuk-2uk + Σuk-2uk-1a + Σuk-22b + Σuk-2c]
dcE = Σ1<k<n -2[ uk - (auk-1 + buk-2 + c)] = 2[-Σuk + Σuk-1a + Σuk-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`.

2. 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.

3. 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