Please complete the following assignment in Jupyter, and upload the file on blackboasrd by midnight on 3 June 2016.

You are strongly encouraged to work out the problems on your own. If you use existing solutions, existing code, help online or collaborate with other students, you will still receive full credit provided that you make this clear and cite your sources. If you collaborate with other students, please submit individual solutions and be specific in giving credit for what each student contributed.

In this assignment we will create a type called `FourFun`

to represent functions periodic on `[0,2π)`

. This will allow us to do the following:

```
n=11 # number of points used
f=FourFun(θ->cos(cos(θ-0.1)),n) # calculate the Fourier coefficients of cos(cos(θ-0.1))
f(0.1) # evaluate the approximate Fourier series at 0.1
plot(f) # plots h
```

We will support addition:

```
g=FourFun(θ->cos(θ),3) # another function with a different number of coefficients
h=f+g # add two Fourier series with different lengths
h(0.5) # should approximate cos(cos(0.4)) + cos(0.5)
```

We will use this type to do signal smoothing:

```
f=FourFun(θ->cos(cos(θ-0.1)) + 0.1randn(),10000)
g=resize(f,-12,12) # drops all but the coefficients between -12 and 12
f(0.5) # should be approximately cos(cos(θ-0.1))
```

The starting point is creating the type `FourFun`

, that will represent the finite Fourier series
$$
\sum_{k=\alpha}^\beta f_k e^{i k \theta}
$$

It has two fields: `negative`

, containing the negative coefficients in *decreasing* order, that is, $[ f_{-1}, f_{-2}, \ldots, f_\alpha]$ and `nonnegative`

, containing the non-negative coefficients in *increasing* order, that is, $[ f_0, f_1, \ldots, f_\beta]$.

In [1]:

```
type FourFun
negative::Vector{Complex128}
nonnegative::Vector{Complex128}
end
```

Out[1]:

**Exercise 1(a)** Complete the following function `FourFun`

that calculates `n`

Fourier coefficients of `f`

, and returns `FourFun`

. You can assume `n`

is an integer, and if desired you can use the `fft`

. (Hint: the `fft`

assumes the values of the function are at $[\theta_0,\theta_1,\ldots,\theta_{n-1}]$ where $\theta_k = {2 \pi k \over n}$. Using the `fft`

will save some time in the last exercise.)

In [ ]:

```
points(n) = linspace(0,2π-2π/n,n)
# INPUT: a Function and an Integer
# OUTPUT: a FourFun whose coefficients correspond to the Fourier series that interpolates
# f at the points [θ_0,θ_1,…,θ_{n-1},θ_n]
function FourFun(f::Function,n::Integer)
# TODO: create a FourFun
end
```

**Exercise 1(b)** Complete the following override of `call`

to evaluate the finite Fourier series represented by `f`

at the point `t`

:

In [4]:

```
import Base.call
# INPUT: a FourFun f and a point 0≤t≤2π
# OUTPUT: The finite Fourier series that f encodes evalauted at t
function call(f::FourFun,t)
# TODO: sum the finite Fourier series encoded by f
end
```

Out[4]:

**Exercise 1(c)** Override `+`

to sum two finite Fourier series. Make sure that you pad the lengths of the vectors! Test that the example at the beginning works.

In [33]:

```
import Base.+
# INPUT: Two FourFuns f and g
# OUTPUT: A FourFun whose nonnegative/negative coefficients are the addition
# of the nonnegative/negative coefficients of f and g. Make sure you pad the
# vectors to have the same length.
#TODO: Override +
```

Out[33]:

**Exercise 2(a)** Override `plot(f::FourFun)`

to plot both the real *and* imaginary parts of the finite Fourier series encoded by `f`

. Make sure the number of plot points depends on the number of coefficients so that the function looks smooth regardless of the length. (Hint: it's faster to use `ifft`

, but not mandatory.)

In [51]:

```
using PyPlot
import PyPlot.plot
function plot(f::FourFun)
# TODO: plot the finite Fourier series encodded by `f`
end
```

Out[51]:

**Exercise 2(b)** Plot `f`

, `g`

and `f+g`

where

```
f=FourFun(θ->cos(cos(θ-0.1)),11)
g=FourFun(θ->cos(θ),3)
```

**Exercise 3(a)** Write a routine `resize(f::FourFun,a,b)`

that resizes the Fourier coefficients to have `-a`

negative coefficients and `b+1`

nonnegative coefficients. You can assume `-a ≤ length(f.negative)`

and `b +1 ≤ length(f.nonnegative)`

.

In [124]:

```
# INPUT: a FourFun f, a negative integer a and a positive integer b
# OUTPUT: a FourFun, with the first -a negative coefficients and
# the first b+1 nonnegative coefficients of f
# TODO: write resize(f::FourFun,a,b)
```

**Exercise 3(b)** Plot the `FourFun`

approximations of

```
f=FourFun(θ->cos(cos(θ-0.1)),25)
noisycos(θ::Number) = cos(cos(θ-0.1)) + 0.1randn()
noisycos(θ::AbstractVector) = cos(cos(θ-0.1)) + 0.1randn(length(θ))
fr=FourFun(noisycos,200)
g=resize(fr,-12,12)
```

In [ ]:

```
```

**Exercise 3(c)** Use a `loglog`

estimate the convergence rate of

```
fr=FourFun(noisycos,n)
g=resize(fr,-12,12)
g(0.1)-cos(cos(0.))
```

as a function of `n`

, as $O(n^{-\gamma})$ where $\gamma$ may not be an integer. This shows that a sufficiently large number of samples allows us to de-noise. (Hint: If you used the `fft`

in exercise *1(a)* this will go faster.)

In [ ]:

```
```